= Chromatic number
{title2=χ(G)}
{wiki}
For a nonempty finite <simple graph> $G$, the <chromatic number> $\chi(G)$ is the least positive <integer> $k$ for which $G$ has a proper vertex <graph coloring> with at most $k$ colours. To establish an exact <chromatic number>, give a colouring using that many colours and explain why fewer cannot suffice. A colouring alone gives only an upper bound.<Mathematics for Computer Science by Eric Lehman and others>[Lehman, Leighton and Meyer, Mathematics for Computer Science, Definition 11.7.1]{ref}
\Image[/graph-coloring-cycle-examples.png]
{title=Optimal <graph colorings> of the <cycle graphs> $C_3,C_4,C_5$}
{description=Numbers inside dots are colour labels, and labels outside are <vertices>. The <cycle graph> $C_4$ alternates two colours. The <odd cycles> $C_3,C_5$ need three, although $C_5$ is a <triangle-free graph>.}
These small <graphs> show why the <chromatic number> measures more than the presence of <triangles in a graph>:
* The <cycle graph> $C_3$, also the <complete graph> $K_3$, has <chromatic number> three. Every pair of <vertices> is adjacent, so three distinct colours are necessary and sufficient.
* The <cycle graph> $C_4$ has <chromatic number> two. Around the <graph cycle>, the assignment $1,2,1,2$ is proper, and a single colour would violate every <edge>.
* The <cycle graph> $C_5$ has <chromatic number> three. With two colours, alternation around the <graph cycle> would force the first and fifth <vertices> to have the same colour despite their joining <edge>. The assignment $1,2,1,2,3$ works. Thus a <triangle-free graph> can still require more than two colours.
* The <complete graph> $K_n$ has <chromatic number> $n$: all $n$ <vertices> are pairwise adjacent, so each must have its own colour.https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2005/5926091844fc3d60fa18eb75c9a2bc03_slides5w.pdf[Meyer, MIT Graph Coloring, slides 18–19]{ref}
For a <cycle graph> of even length, alternating two colours closes consistently; for an <odd cycle>, it does not, and a third colour on the final <vertex> suffices. More generally, the <two-colourability criterion for bipartite graphs> says that $\chi(G)\leq2$ exactly when $G$ is a <bipartite graph>, and the <odd-cycle characterization of bipartite graphs> identifies the obstruction as an <odd cycle>. A nonempty <graph> with no <edges> has <chromatic number> one; a <bipartite graph> with at least one <edge> has <chromatic number> exactly two.
In the pairwise-conflict scheduling model of <graph coloring>, $\chi(G)$ is the least number of interchangeable slots needed. This turns a drawing into an optimization question: how many groups of compatible activities are unavoidable? <Greedy coloring> constructs a valid grouping quickly, but its number of colours can exceed the <chromatic number>.
Back to article page
