Everipedia Logo
Everipedia is now IQ.wiki - Join the IQ Brainlist and our Discord for early access to editing on the new platform and to participate in the beta testing.
Brooks' theorem

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. 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).

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]

References

[1]
Citation Linkopenlibrary.orgAlon, Noga; Krivelevich, Michael; Sudakov, Benny (1999), "Coloring graphs with sparse neighborhoods", Journal of Combinatorial Theory, Series B, 77 (1): 73–82, doi:10.1006/jctb.1999.1910.
Sep 21, 2019, 12:04 AM
[2]
Citation Linkopenlibrary.orgSkulrattanakulchai, San (2006), "Δ-List vertex coloring in linear time", Information Processing Letters, 98 (3): 101–106, doi:10.1016/j.ipl.2005.12.007.
Sep 21, 2019, 12:04 AM
[3]
Citation Linkopenlibrary.orgKarloff, H. J. (1989), "An NC algorithm for Brooks' theorem", Theoretical Computer Science, 68 (1): 89–103, doi:10.1016/0304-3975(89)90121-7; Hajnal, Péter; Szemerédi, Endre (1990), "Brooks coloring in parallel", SIAM Journal on Discrete Mathematics, 3 (1): 74–80, doi:10.1137/0403008; Panconesi, Alessandro; Srinivasan, Aravind (1995), "The local nature of Δ-coloring and its algorithmic applications", Combinatorica, 15 (2): 255–280, doi:10.1007/BF01200759; 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.
Sep 21, 2019, 12:04 AM
[4]
Citation Link//doi.org/10.1017%2FS030500410002168X10.1017/S030500410002168X
Sep 21, 2019, 12:04 AM
[5]
Citation Link//doi.org/10.1016%2F0095-8956%2875%2990089-110.1016/0095-8956(75)90089-1
Sep 21, 2019, 12:04 AM
[6]
Citation Link//doi.org/10.1006%2Fjctb.1998.189110.1006/jctb.1998.1891
Sep 21, 2019, 12:04 AM
[7]
Citation Linkmathworld.wolfram.com"Brooks' Theorem"
Sep 21, 2019, 12:04 AM
[8]
Citation Linkdoi.org10.1006/jctb.1999.1910
Sep 21, 2019, 12:04 AM
[9]
Citation Linkdoi.org10.1016/j.ipl.2005.12.007
Sep 21, 2019, 12:04 AM
[10]
Citation Linkdoi.org10.1016/0304-3975(89)90121-7
Sep 21, 2019, 12:04 AM
[11]
Citation Linkdoi.org10.1137/0403008
Sep 21, 2019, 12:04 AM
[12]
Citation Linkdoi.org10.1007/BF01200759
Sep 21, 2019, 12:04 AM
[13]
Citation Linkdoi.org10.1006/jagm.2000.1097
Sep 21, 2019, 12:04 AM
[14]
Citation Linkdoi.org10.1017/S030500410002168X
Sep 21, 2019, 12:04 AM
[15]
Citation Linkdoi.org10.1016/0095-8956(75)90089-1
Sep 21, 2019, 12:04 AM
[16]
Citation Linkdoi.org10.1006/jctb.1998.1891
Sep 21, 2019, 12:04 AM
[17]
Citation Linkmathworld.wolfram.com"Brooks' Theorem"
Sep 21, 2019, 12:04 AM
[18]
Citation Linken.wikipedia.orgThe original version of this page is from Wikipedia, you can edit the page right here on Everipedia.Text is available under the Creative Commons Attribution-ShareAlike License.Additional terms may apply.See everipedia.org/everipedia-termsfor further details.Images/media credited individually (click the icon for details).
Sep 21, 2019, 12:04 AM