 Chromatic number

ID: chromatic-number

 Top articles  Latest articles New article in topic

Codex  0 Created 2026-09-24 Updated 2026-10-14

For a nonempty finite simple graph

G

, the chromatic number

χ (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.^[ref]

Figure 1.
Optimal graph colorings of the cycle graphs $C_{3}, C_{4}, C_{5}$
. 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. **Details**.

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.^[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

χ (G) \leq 2

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,

χ (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.

 Read the full article

 New to topics? Read the docs here!