Chromatic number & colouring bounds
The chromatic number χ(G) is the fewest colours needed so that adjacent vertices differ. Bounding it from below usually means exhibiting a clique — χ ≥ ω(G) — and from above means giving an explicit colouring, with greedy guaranteeing χ ≤ Δ + 1. Brooks’ theorem sharpens this to χ ≤ Δ except for complete graphs and odd cycles.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Find a large clique for a lower boundA set of k mutually adjacent vertices forces at least k colours.
- Colour greedily for an upper boundOrder the vertices and give each the smallest colour unused by its neighbours. This never needs more than Δ + 1.
- Squeeze the bounds togetherIf a clique of size k exists and you produce a k-colouring, then χ = k exactly — no further work needed.
- Use structural factsχ = 1 iff no edges; χ ≤ 2 iff bipartite (no odd cycle); planar graphs satisfy χ ≤ 4.
Worked example
Find χ(C₅) and χ(K₄).
- C₅ has edges, so χ ≥ 2. But it is an odd cycle, so it is not bipartite and χ ≥ 3.
- Colour it 1,2,1,2,3 around the cycle — a valid 3-colouring.
- K₄ has all four vertices mutually adjacent, so all must differ: χ ≥ 4.
- Four colours obviously suffice.
Answer. χ(C₅) = 3 and χ(K₄) = 4.
Where marks get dropped
These are the specific errors that cost credit on chromatic number & colouring bounds questions — QED's rubric penalises each of them separately.
- Assuming a large maximum degree forces many colours. A star K_{1,n} has Δ = n but χ = 2.
- Treating the greedy bound as exact. Greedy colouring depends on vertex order and can use far more than χ colours.
- Forgetting the exceptions in Brooks’ theorem — complete graphs and odd cycles genuinely need Δ + 1.
Practise this until it is automatic
Unlimited fresh questions
QED generates new chromatic number & colouring bounds problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.
Chromatic number & colouring bounds — frequently asked questions
Is computing χ hard?
Yes — determining whether χ ≤ 3 is NP-complete. Even approximating χ well is hard, so exam questions stay small or structured.
What is the four colour theorem?
Every planar graph has χ ≤ 4. Proved in 1976 with substantial computer assistance, and still with no short human-checkable proof.
How does χ relate to independent sets?
A colour class is an independent set, so χ ≥ n/α(G) where α is the largest independent set size. Colouring is exactly partitioning into independent sets.
The rest of Graphs
Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Degrees & the handshake lemma
- 2Paths, cycles, connectivity & components
- 3Trees & their properties
- 4Bipartite graphs & colouring basics
- 5Euler & Hamilton paths and circuits
- 6Adjacency matrices & isomorphism
- 7Degree sequences & graphic sequences
- 8Spanning trees: Kruskal & Prim
- 9Shortest paths with Dijkstra
- 10Planarity & Euler’s formula
- 11Directed graphs, in-degree & out-degree
- 12Binary trees: height, traversals & counting
- 13Chromatic number & colouring bounds
- 14Matchings & Hall’s marriage theorem
Ready to make chromatic number & colouring bounds exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →