6 Graph Colouring
In this section, we shall assume (except where noted) that graphs are loopless.
Upper and Lower Bounds
Colouring: A k-colouring of a graph G is a map φ : V (G) → S where |S| = k with the
property that φ(u) 6= φ(v) whenever there is an edge with ends u, v. The elements of S are
called colours, and the vertices of one colour form a colour class. The chromatic number of
G, denoted χ(G), is the smallest integer k such that G is k-colourable. If G has a loop, then
it does not have a colouring, and we set χ(G) = ∞.
Independent Set: A set of vertices is independent if they are pairwise nonadjacent. We
let α(G) denote the size of the largest independent set in G. Note that in a colouring, every
colour class is an independent set.
Clique: A set of vertices is a clique if they are pairwise adjacent. We let ω(G) denote the
size of the largest clique in G.
Observation 6.1
χ(G) ≥ ω(G)
|V (G)|
χ(G) ≥
α(G)
Proof: The first part follows from the observation that any two vertices in a clique must
receive different colours. The second follows from the observation that each colour class in
a colouring has size ≤ α(G). ¤
Greedy Algorithm: Order the vertices v1 , v2 , . . . , vn and then colour them (using positive
integers) in order by assigning to vi the smallest possible integer which is not already used
on a neighbor of vi .
Maximum and Minimum Degree: We let ∆(G) denote the maximum degree of a vertex
in G and we let δ(G) denote the minimum degree of a vertex in G.
Degeneracy: A graph G is k-degenerate if every subgraph of G has a vertex of degree at
most k.
, 2
Observation 6.2
χ(G) ≤ ∆(G) + 1
χ(G) ≤ k + 1 if G is k-degenerate
Proof: The first part follows by applying the greedy algorithm to any ordering of V (G).
For the second part, let |V (G)| = n, and order the vertices starting from the back and
working forward by the rule that vi is chosen to be a vertex of degree ≤ k in the graph
G − {vi+1 , vi+2 , . . . , vn }. When the greedy algorithm is applied to this ordering, each vertex
has ≤ k neighbors preceding it, so we obtain a colouring with ≤ k + 1 colours as desired.
¤
Theorem 6.3 (Brooks) If G is a connected graph which is not complete and not an odd
cycle, then χ(G) ≤ ∆(G).
Proof: Let ∆ = ∆(G). If G is (∆ − 1)-degenerate, then we are done by the previous
observation. Thus, we may assume that there is a subgraph H ⊆ G so that H has minimum
degree ∆. But then H must be ∆-regular, and no vertex in H can have a neighbor outside
V (H), so we find that H = G. It follows from this that G is ∆-regular and every proper
subgraph of H is (∆ − 1)-degenerate. The theorem is trivial if ∆ = 2, so we may further
assume that ∆ ≥ 3.
If G has a proper 1-separation (H1 , H2 ), then H1 and H2 are (∆ − 1)-degenerate, so
each of these graphs is ∆-colourable. By permuting colours in the colouring of H2 , we may
arrange that these two ∆-colourings assign the same colour to the vertex in V (H1 ) ∩ V (H2 ),
and then combining these colourings gives a ∆-colouring of G. Thus, we may assume that
G is 2-connected.
If G is 3-connected, choose vn ∈ V (G). If every pair of neighbors of vn are adjacent, then
G is a complete graph and we are finished. Otherwise, let v1 , v2 be neighbors of vn , and note
that G − {v1 , v2 } is connected.
If G is not 3-connected, choose vn ∈ V (G) so that G − vn is not 2-connected. Consider
the block-cutpoint graph of G − vn , and for i = 1, 2, let Hi be a leaf block of G − vn which
is adjacent in the block-cutpoint graph to the cut-vertex xi . Since G is 2-connected, for
i = 1, 2 there exists a vertex vi ∈ V (Hi ) \ {xi } which is adjacent to vn . Note that because
In this section, we shall assume (except where noted) that graphs are loopless.
Upper and Lower Bounds
Colouring: A k-colouring of a graph G is a map φ : V (G) → S where |S| = k with the
property that φ(u) 6= φ(v) whenever there is an edge with ends u, v. The elements of S are
called colours, and the vertices of one colour form a colour class. The chromatic number of
G, denoted χ(G), is the smallest integer k such that G is k-colourable. If G has a loop, then
it does not have a colouring, and we set χ(G) = ∞.
Independent Set: A set of vertices is independent if they are pairwise nonadjacent. We
let α(G) denote the size of the largest independent set in G. Note that in a colouring, every
colour class is an independent set.
Clique: A set of vertices is a clique if they are pairwise adjacent. We let ω(G) denote the
size of the largest clique in G.
Observation 6.1
χ(G) ≥ ω(G)
|V (G)|
χ(G) ≥
α(G)
Proof: The first part follows from the observation that any two vertices in a clique must
receive different colours. The second follows from the observation that each colour class in
a colouring has size ≤ α(G). ¤
Greedy Algorithm: Order the vertices v1 , v2 , . . . , vn and then colour them (using positive
integers) in order by assigning to vi the smallest possible integer which is not already used
on a neighbor of vi .
Maximum and Minimum Degree: We let ∆(G) denote the maximum degree of a vertex
in G and we let δ(G) denote the minimum degree of a vertex in G.
Degeneracy: A graph G is k-degenerate if every subgraph of G has a vertex of degree at
most k.
, 2
Observation 6.2
χ(G) ≤ ∆(G) + 1
χ(G) ≤ k + 1 if G is k-degenerate
Proof: The first part follows by applying the greedy algorithm to any ordering of V (G).
For the second part, let |V (G)| = n, and order the vertices starting from the back and
working forward by the rule that vi is chosen to be a vertex of degree ≤ k in the graph
G − {vi+1 , vi+2 , . . . , vn }. When the greedy algorithm is applied to this ordering, each vertex
has ≤ k neighbors preceding it, so we obtain a colouring with ≤ k + 1 colours as desired.
¤
Theorem 6.3 (Brooks) If G is a connected graph which is not complete and not an odd
cycle, then χ(G) ≤ ∆(G).
Proof: Let ∆ = ∆(G). If G is (∆ − 1)-degenerate, then we are done by the previous
observation. Thus, we may assume that there is a subgraph H ⊆ G so that H has minimum
degree ∆. But then H must be ∆-regular, and no vertex in H can have a neighbor outside
V (H), so we find that H = G. It follows from this that G is ∆-regular and every proper
subgraph of H is (∆ − 1)-degenerate. The theorem is trivial if ∆ = 2, so we may further
assume that ∆ ≥ 3.
If G has a proper 1-separation (H1 , H2 ), then H1 and H2 are (∆ − 1)-degenerate, so
each of these graphs is ∆-colourable. By permuting colours in the colouring of H2 , we may
arrange that these two ∆-colourings assign the same colour to the vertex in V (H1 ) ∩ V (H2 ),
and then combining these colourings gives a ∆-colouring of G. Thus, we may assume that
G is 2-connected.
If G is 3-connected, choose vn ∈ V (G). If every pair of neighbors of vn are adjacent, then
G is a complete graph and we are finished. Otherwise, let v1 , v2 be neighbors of vn , and note
that G − {v1 , v2 } is connected.
If G is not 3-connected, choose vn ∈ V (G) so that G − vn is not 2-connected. Consider
the block-cutpoint graph of G − vn , and for i = 1, 2, let Hi be a leaf block of G − vn which
is adjacent in the block-cutpoint graph to the cut-vertex xi . Since G is 2-connected, for
i = 1, 2 there exists a vertex vi ∈ V (Hi ) \ {xi } which is adjacent to vn . Note that because
