# 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

László Lovász (1975) 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 Vadim Vizing (1976). 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. Bruce Reed (1999) 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.^{[1]}

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.^{[2]} Efficient algorithms are also known for finding Brooks colorings in parallel and distributed models of computation.^{[3]}

## Notes

## References

- "Coloring graphs with sparse neighborhoods",
*Journal of Combinatorial Theory*, Series B**77**(1): 73–82, 1999, doi:10.1006/jctb.1999.1910 - "On colouring the nodes of a network",
*Mathematical Proceedings of the Cambridge Philosophical Society***37**(2): 194–197, 1941, doi:10.1017/S030500410002168X, Bibcode: 1941PCPS...37..194B. - Grable, David A.; Panconesi, Alessandro (2000), "Fast distributed algorithms for Brooks–Vizing colourings",
*Journal of Algorithms***37**: 85–120, doi:10.1006/jagm.2000.1097. - Hajnal, Péter (1990), "Brooks coloring in parallel",
*SIAM Journal on Discrete Mathematics***3**(1): 74–80, doi:10.1137/0403008. - Karloff, H. J. (1989), "An NC algorithm for Brooks' theorem",
*Theoretical Computer Science***68**(1): 89–103, doi:10.1016/0304-3975(89)90121-7. - "Three short proofs in graph theory",
*Journal of Combinatorial Theory*, Series B**19**(3): 269–271, 1975, doi:10.1016/0095-8956(75)90089-1. - Panconesi, Alessandro; Srinivasan, Aravind (1995), "The local nature of Δ-coloring and its algorithmic applications",
*Combinatorica***15**(2): 255–280, doi:10.1007/BF01200759. - "A strengthening of Brooks' theorem",
*Journal of Combinatorial Theory*, Series B**76**(2): 136–149, 1999, doi:10.1006/jctb.1998.1891. - Skulrattanakulchai, San (2006), "Δ-List vertex coloring in linear time",
*Information Processing Letters***98**(3): 101–106, doi:10.1016/j.ipl.2005.12.007. - Vizing, V. G. (1976), "Vertex colorings with given colors" (in Russian),
*Diskret. Analiz.***29**: 3–10.

## External links

Original source: https://en.wikipedia.org/wiki/Brooks' theorem.
Read more |