What is Brook's theorem?

Brook’s theorem states that the chromatic number χ(G) ≤ Δ(G) + 1, where Δ(G) is the maximum degree of a vertex of G. Equality holds only for odd-length cycles (which have chromatic number 3) and complete graphs.

Submit