maths.free › Discrete Math & Logic › Graph colouring
Graph colouring
Proper colourings, chromatic number, bipartite graphs, greedy colouring and the chromatic polynomial.
A proper colouring assigns a colour to each vertex so that adjacent vertices get different colours. The chromatic number \( \chi(G) \) is the fewest colours that suffice. Colouring models conflicts: exams that share a student cannot be at the same time, radio transmitters that are close cannot share a frequency, and variables that are live together cannot share a register. The colours are the time slots, frequencies or registers.
Some values are immediate. \( \chi(K_n) = n \), since every pair conflicts. A graph with at least one edge needs 2 colours, and it can be coloured with exactly 2 if and only if it is bipartite, which happens if and only if it has no cycle of odd length. So even cycles have chromatic number 2 and odd cycles have 3. Any graph containing \( K_r \) needs at least \( r \) colours, although a graph can need many colours without containing even a triangle.
The greedy algorithm colours vertices one at a time, giving each the smallest colour not used by its already coloured neighbours. A vertex has at most \( \Delta \) neighbours, where \( \Delta \) is the largest degree, so greedy never needs more than \( \Delta + 1 \) colours: \( \chi(G) \le \Delta + 1 \). The bound is reached by complete graphs and odd cycles, and Brooks' theorem says those are the only connected examples. For graphs that can be drawn in the plane without crossings, four colours always suffice: this is the four colour theorem, proved by Appel and Haken in 1976 with a computer check of a large set of configurations (five colours are much easier to prove).
The chromatic polynomial \( P(G, k) \) counts proper colourings using at most \( k \) colours. For a path on \( n \) vertices, colour the vertices in order: \( k \) choices for the first and \( k - 1 \) for each of the others, so \( P = k(k-1)^{n-1} \). For a triangle, \( k(k-1)(k-2) \), which the example expands; it vanishes at \( k = 0, 1, 2 \) and first becomes positive at \( k = 3 = \chi \). In general \( \chi(G) \) is the smallest positive integer that is not a root, and the deletion-contraction rule \( P(G, k) = P(G - e, k) - P(G / e, k) \) computes the polynomial for any graph.
Picture it: a map of regions with a dot in each and a line between neighbours. Colouring the map so no two neighbours match is colouring that graph. An odd cycle is a ring of an odd number of countries: alternating two colours around it always fails at the last step.
Think it: to show \( \chi(G) = r \) you need two arguments: a colouring with \( r \) colours (the upper bound) and a reason \( r - 1 \) cannot work, such as an odd cycle or a \( K_r \) subgraph (the lower bound). Deciding whether a graph can be 3-coloured is NP-complete, so no fast general method is known, even though checking a proposed colouring is easy.
Worked example · expand k*(k-1)*(k-2)
Now you Pick a problem, or type or draw your own. Every step, a picture, the answer hidden until you ask.
Symbols used here
Tap any symbol for the full definition, a picture, and what every letter in it means.
How to: Graph colouring
- Look for a lower bound: a K_r subgraph needs r colours, an odd cycle needs 3.
- Find a colouring that meets the lower bound, greedily or by hand.
- For two colours, try to 2-colour by breadth-first search; an odd cycle is the only thing that can stop you.
- For the chromatic polynomial, colour vertex by vertex for paths and trees, or use deletion-contraction.
Questions people ask
Is every tree 2-colourable?
Yes, if it has at least one edge. A tree has no cycles at all, odd or even, so it is bipartite: colour vertices by whether their distance from a fixed root is even or odd.
Why does greedy colouring sometimes use too many colours?
Its result depends on the order of the vertices. On some bipartite graphs a bad order forces many colours, although there is always some order for which greedy uses exactly the chromatic number.
What makes mathematics "discrete"?
It deals with separate, countable objects (integers, graphs, statements) rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.
How does a proof by induction work?
Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.
What order should I take these lessons in?
Logic and proof first, because every later lesson proves things. Then induction, sets, relations and functions, counting, recurrences, graphs, Boolean algebra and automata, and finally algorithms and complexity, which use nearly everything before them.
Is discrete mathematics the same as the maths of computer science?
Largely. Data structures are graphs and trees, correctness arguments are induction, running times are recurrences and sums, circuits are Boolean algebra, and what a computer can do efficiently is the subject of the last lessons. It is also ordinary mathematics in its own right.
Do I need calculus for this course?
No. School algebra is enough. A little familiarity with limits helps when comparing growth rates, and the lesson on asymptotic analysis explains the one limit fact it uses.
More in Discrete Math & Logic
Truth tablesSums and inductionProof by inductionAlgorithms and growth of functionsPredicate logic and quantifiersDirect proof, contrapositive and contradictionStrong induction and the well-ordering principleRelations: equivalence relations and partial ordersFunctions and cardinalityCounting: rules, choices and bijectionsThe pigeonhole principleSolving linear recurrence relationsGraphs: degrees, paths and connectivityTrees and spanning trees