Brooks' Theorem

In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors.

The theorem is named after R. Leonard Brooks, who published a proof of it in 1941. A coloring with the number of colors described by Brooks' theorem is sometimes called a ''Brooks coloring'' or a Δ-''coloring''.

Formal statement

For any connected undirected graph ''G'' with maximum degree Δ,
the chromatic number of ''G'' is at most Δ, unless ''G'' is a complete graph or an odd cycle, in which case the chromatic number is Δ + 1.

Proof

gives a simplified proof of Brooks' theorem. If the graph is not biconnected, its biconnected components may be colored separately and then the colorings combined. If the graph has a vertex ''v'' with degree less than Δ, then a greedy coloring algorithm that colors vertices farther from ''v'' before closer ones uses at most Δ colors. This is because at the time that each vertex other than ''v'' is colored, at least one of its neighbors (the one on a shortest path to ''v'') is uncolored, so it has fewer than Δ colored neighbors and has a free color. When the algorithm reaches ''v'', its small number of neighbors allows it to be colored. Therefore, the most difficult case of the proof concerns biconnected Δ-regular graphs with Δ ≥ 3. In this case, Lovász shows that one can find a spanning tree such that two nonadjacent neighbors ''u'' and ''w'' of the root ''v'' are leaves in the tree. A greedy coloring starting from ''u'' and ''w'' and processing the remaining vertices of the spanning tree in bottom-up order, ending at ''v'', uses at most Δ colors. For, when every vertex other than ''v'' is colored, it has an uncolored parent, so its already-colored neighbors cannot use up all the free colors, while at ''v'' the two neighbors ''u'' and ''w'' have equal colors so again a free color remains for ''v'' itself.

Extensions

A more general version of the theorem applies to list coloring: given any connected undirected graph with maximum degree Δ that is neither a clique nor an odd cycle, and a list of Δ colors for each vertex, it is possible to choose a color for each vertex from its list so that no two adjacent vertices have the same color. In other words, the list chromatic number of a connected undirected graph G never exceeds Δ, unless G is a clique or an odd cycle. This has been proved by . A small modification of the proof of Lovász applies to this case: for the same three vertices ''u'', ''v'', and ''w'' from that proof, either give ''u'' and ''w'' the same color as each other (if possible), or otherwise give one of them a color that is unavailable to ''v'', and then complete the coloring greedily as before.

For certain graphs, even fewer than Δ colors may be needed. shows that Δ − 1 colors suffice if and only if the given graph has no Δ-clique, ''provided'' Δ is large enough. For triangle-free graphs, or more generally graphs in which the neighborhood of every vertex is sufficiently sparse, O(Δ/log Δ) colors suffice.

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. An extension of Brooks' theorem to total coloring, stating that the total chromatic number is at most Δ + 2, has been conjectured by Mehdi Behzad and Vizing. The Hajnal–Szemerédi theorem on equitable coloring states that any graph has a (Δ + 1)-coloring in which the sizes of any two color classes differ by at most one.

Algorithms

A Δ-coloring, or even a Δ-list-coloring, of a degree-Δ graph may be found in linear time. Efficient algorithms are also known for finding Brooks colorings in parallel and distributed models of computation.; ; ; .

Notes

References

*
*.
*.
*.
*.
*.
*.
*.
*.
*.

External links

*{{mathworld, title=Brooks' Theorem, urlname=BrooksTheorem, mode=cs2

Graph coloring
Theorems in graph theory