For a connected graph G, the chromatic number χ(G) ≤ Δ(G) (the maximum degree) unless G is a complete graph or an odd cycle. Tightens the trivial Δ+1 bound. Proved by R. L. Brooks in 1941.
For a connected graph G, the chromatic number χ(G) ≤ Δ(G) (the maximum degree) unless G is a complete graph or an odd cycle. Tightens the trivial Δ+1 bound. Proved by R. L. Brooks in 1941.