Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Brooks' theorem
open-in-new
<h2 id="formal-statement">Formal statement</h2> <p>For any <a href="/facts/Connected_graph/FSNjsYhz">connected</a> <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> <i>G</i> with maximum <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> Δ, the <a href="/facts/Chromatic_number/J6HoBfP0">chromatic number</a> of <i>G</i> is at most Δ, unless <i>G</i> is a complete graph or an odd cycle, in which case the chromatic number is Δ + 1.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <h2 id="proof">Proof</h2> <p><a href="/facts/L%25C3%25A1szl%25C3%25B3_Lov%25C3%25A1sz/X0VB38Ee">László Lovász</a> gives a simplified proof of Brooks' theorem. If the graph is not <a href="/facts/Biconnected_graph/sTfSnFkM">biconnected</a>, its biconnected components may be colored separately and then the colorings combined. If the graph has a vertex <i>v</i> with degree less than Δ, then a <a href="/facts/Greedy_coloring/mKpxpQuG">greedy coloring</a> algorithm that colors vertices farther from <i>v</i> before closer ones uses at most Δ colors. This is because at the time that each vertex other than <i>v</i> is colored, at least one of its neighbors (the one on a shortest path to <i>v</i>) is uncolored, so it has fewer than Δ colored neighbors and has a free color. When the algorithm reaches <i>v</i>, its small number of neighbors allows it to be colored. Therefore, the most difficult case of the proof concerns biconnected Δ-<a href="/facts/Regular_graph/j9dSoLE6">regular</a> graphs with Δ ≥ 3. In this case, Lovász shows that one can find a <a href="/facts/Spanning_tree/qQPN9taR">spanning tree</a> such that two nonadjacent neighbors <i>u</i> and <i>w</i> of the root <i>v</i> are leaves in the tree. A greedy coloring starting from <i>u</i> and <i>w</i> and processing the remaining vertices of the spanning tree in bottom-up order, ending at <i>v</i>, uses at most Δ colors. For, when every vertex other than <i>v</i> is colored, it has an uncolored parent, so its already-colored neighbors cannot use up all the free colors, while at <i>v</i> the two neighbors <i>u</i> and <i>w</i> have equal colors so again a free color remains for <i>v</i> itself.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p> <h2 id="extensions">Extensions</h2> <p>A more general version of the theorem applies to <a href="/facts/List_coloring/fXV2lcSh">list coloring</a>: given any connected undirected graph with maximum degree Δ that is neither a <a href="/facts/Clique_(graph_theory)/XK9ppLz5">clique</a> 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.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p><p>For certain graphs, even fewer than Δ colors may be needed. Δ − 1 colors suffice if and only if the given graph has no Δ-clique, <i>provided</i> Δ is large enough.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> For <a href="/facts/Triangle-free_graph/8D3LJ44h">triangle-free graphs</a>, or more generally graphs in which the <a href="/facts/Neighborhood_(graph_theory)/E6V1hk6b">neighborhood</a> of every vertex is sufficiently <a href="/facts/Sparse_graph/xFC7b7s9">sparse</a>, O(Δ/log Δ) colors suffice.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p><p>The degree of a graph also appears in upper bounds for other types of coloring; for <a href="/facts/Edge_coloring/AcdpUxCv">edge coloring</a>, the result that the chromatic index is at most Δ + 1 is <a href="/facts/Vizing%2527s_theorem/hHtEtK9t">Vizing's theorem</a>. An extension of Brooks' theorem to <a href="/facts/Total_coloring/CwxcyopP">total coloring</a>, stating that the total chromatic number is at most Δ + 2, has been conjectured by <a href="/facts/Mehdi_Behzad/zuRtBAqW">Mehdi Behzad</a> and Vizing. The Hajnal–Szemerédi theorem on <a href="/facts/Equitable_coloring/fchI6knh">equitable coloring</a> states that any graph has a (Δ + 1)-coloring in which the sizes of any two color classes differ by at most one. </p> <h2 id="algorithms">Algorithms</h2> <p>A Δ-coloring, or even a Δ-list-coloring, of a degree-Δ graph may be found in linear time.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> Efficient algorithms are also known for finding Brooks colorings in parallel and distributed models of computation.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> </p> <h2 id="notes">Notes</h2> <ul><li><a href="/facts/Noga_Alon/tuqq2GUl">Alon, Noga</a>; <a href="/facts/Michael_Krivelevich/PvTMGDv6">Krivelevich, Michael</a>; <a href="/facts/Benny_Sudakov/gYyxp5ym">Sudakov, Benny</a> (1999), "Coloring graphs with sparse neighborhoods", <i><a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a></i>, Series B, 77 (1): 73–82, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1006%2Fjctb.1999.1910">10.1006/jctb.1999.1910</a></li> <li><a href="/facts/R._Leonard_Brooks/ykCDCwTX">Brooks, R. L.</a> (1941), "On colouring the nodes of a network", <i><a href="/facts/Mathematical_Proceedings_of_the_Cambridge_Philosophical_Society/KUUzcS7S">Mathematical Proceedings of the Cambridge Philosophical Society</a></i>, 37 (2): 194–197, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1941PCPS...37..194B">1941PCPS...37..194B</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1017%2FS030500410002168X">10.1017/S030500410002168X</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:209835194">209835194</a>.</li> <li>Grable, David A.; Panconesi, Alessandro (2000), "Fast distributed algorithms for Brooks–Vizing colourings", <i>Journal of Algorithms</i>, 37: 85–120, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1006%2Fjagm.2000.1097">10.1006/jagm.2000.1097</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14211416">14211416</a>.</li> <li>Hajnal, Péter; <a href="/facts/Endre_Szemer%25C3%25A9di/bE2Ezgbl">Szemerédi, Endre</a> (1990), "Brooks coloring in parallel", <i><a href="/facts/SIAM_Journal_on_Discrete_Mathematics/7BG23qL5">SIAM Journal on Discrete Mathematics</a></i>, 3 (1): 74–80, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0403008">10.1137/0403008</a>.</li> <li>Karloff, H. J. (1989), "An NC algorithm for Brooks' theorem", <i>Theoretical Computer Science</i>, 68 (1): 89–103, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0304-3975%2889%2990121-7">10.1016/0304-3975(89)90121-7</a>.</li> <li><a href="/facts/L%25C3%25A1szl%25C3%25B3_Lov%25C3%25A1sz/X0VB38Ee">Lovász, L.</a> (1975), "Three short proofs in graph theory", <i><a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a></i>, Series B, 19 (3): 269–271, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0095-8956%2875%2990089-1">10.1016/0095-8956(75)90089-1</a>.</li> <li>Panconesi, Alessandro; Srinivasan, Aravind (1995), "The local nature of Δ-coloring and its algorithmic applications", <i><a href="/facts/Combinatorica/AxdqUqrp">Combinatorica</a></i>, 15 (2): 255–280, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2FBF01200759">10.1007/BF01200759</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:28307157">28307157</a>.</li> <li><a href="/facts/Bruce_Reed_(mathematician)/rwrfNHpG">Reed, Bruce</a> (1999), "A strengthening of Brooks' theorem", <i><a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a></i>, Series B, 76 (2): 136–149, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1006%2Fjctb.1998.1891">10.1006/jctb.1998.1891</a>.</li> <li>Skulrattanakulchai, San (2006), "Δ-List vertex coloring in linear time", <i><a href="/facts/Information_Processing_Letters/e2u7fEKe">Information Processing Letters</a></i>, 98 (3): 101–106, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ipl.2005.12.007">10.1016/j.ipl.2005.12.007</a>.</li> <li>Vizing, V. G. (1976), "Vertex colorings with given colors", <i>Diskret. Analiz.</i> (in Russian), 29: 3–10.</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a>, <a href="https://mathworld.wolfram.com/BrooksTheorem.html">"Brooks' Theorem"</a>, <i><a href="/facts/MathWorld/yc1jodbq">MathWorld</a></i></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Brooks (1941). - Brooks, R. L. (1941), "On colouring the nodes of a network", Mathematical Proceedings of the Cambridge Philosophical Society, 37 (2): 194–197, Bibcode:1941PCPS...37..194B, doi:10.1017/S030500410002168X, S2CID 209835194 <a href="https://ui.adsabs.harvard.edu/abs/1941PCPS...37..194B" target="_blank">https://ui.adsabs.harvard.edu/abs/1941PCPS...37..194B</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Hajnal & Szemerédi (1990). - Hajnal, Péter; Szemerédi, Endre (1990), "Brooks coloring in parallel", SIAM Journal on Discrete Mathematics, 3 (1): 74–80, doi:10.1137/0403008 <a href="https://doi.org/10.1137%2F0403008" target="_blank">https://doi.org/10.1137%2F0403008</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Panconesi & Srinivasan (1995). - Panconesi, Alessandro; Srinivasan, Aravind (1995), "The local nature of Δ-coloring and its algorithmic applications", Combinatorica, 15 (2): 255–280, doi:10.1007/BF01200759, S2CID 28307157 <a href="https://doi.org/10.1007%2FBF01200759" target="_blank">https://doi.org/10.1007%2FBF01200759</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Brooks (1941). - Brooks, R. L. (1941), "On colouring the nodes of a network", Mathematical Proceedings of the Cambridge Philosophical Society, 37 (2): 194–197, Bibcode:1941PCPS...37..194B, doi:10.1017/S030500410002168X, S2CID 209835194 <a href="https://ui.adsabs.harvard.edu/abs/1941PCPS...37..194B" target="_blank">https://ui.adsabs.harvard.edu/abs/1941PCPS...37..194B</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Lovász (1975). - Lovász, L. (1975), "Three short proofs in graph theory", Journal of Combinatorial Theory, Series B, 19 (3): 269–271, doi:10.1016/0095-8956(75)90089-1 <a href="https://doi.org/10.1016%2F0095-8956%2875%2990089-1" target="_blank">https://doi.org/10.1016%2F0095-8956%2875%2990089-1</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Vizing (1976). - Vizing, V. G. (1976), "Vertex colorings with given colors", Diskret. Analiz. (in Russian), 29: 3–10 <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Reed (1999). - Reed, Bruce (1999), "A strengthening of Brooks' theorem", Journal of Combinatorial Theory, Series B, 76 (2): 136–149, doi:10.1006/jctb.1998.1891 <a href="https://doi.org/10.1006%2Fjctb.1998.1891" target="_blank">https://doi.org/10.1006%2Fjctb.1998.1891</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Alon, Krivelevich & Sudakov (1999). - Alon, 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 <a href="https://doi.org/10.1006%2Fjctb.1999.1910" target="_blank">https://doi.org/10.1006%2Fjctb.1999.1910</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Skulrattanakulchai (2006). - Skulrattanakulchai, San (2006), "Δ-List vertex coloring in linear time", Information Processing Letters, 98 (3): 101–106, doi:10.1016/j.ipl.2005.12.007 <a href="https://doi.org/10.1016%2Fj.ipl.2005.12.007" target="_blank">https://doi.org/10.1016%2Fj.ipl.2005.12.007</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Karloff (1989); Hajnal & Szemerédi (1990); Panconesi & Srinivasan (1995); Grable & Panconesi (2000). - 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 <a href="https://doi.org/10.1016%2F0304-3975%2889%2990121-7" target="_blank">https://doi.org/10.1016%2F0304-3975%2889%2990121-7</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> </ol>