Brooks' theorem

Therefore, the most difficult case of the proof concerns biconnected Δ-regular graphs with Δ ≥ 3.

In other words, the list chromatic number of a connected undirected graph G never exceeds Δ, unless G is a clique or an odd cycle.

[7] The degree of a graph also appears in upper bounds for other types of coloring; for edge coloring, the result that the chromatic index is at most Δ + 1 is Vizing's theorem.

A Δ-coloring, or even a Δ-list-coloring, of a degree-Δ graph may be found in linear time.

[8] Efficient algorithms are also known for finding Brooks colorings in parallel and distributed models of computation.

Complete graphs need one more color than their maximum degree. They and the odd cycles are the only exceptions to Brooks' theorem.