Brooks' theorem

Quality 0.50 · 4 views · Updated 2 months ago

On graph coloring and neighborhood size

title: "Brooks' theorem" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-coloring", "theorems-in-graph-theory"] description: "On graph coloring and neighborhood size" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Brooks'_theorem" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary On graph coloring and neighborhood size ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/6/6a/Graph_exact_coloring.svg" caption="[[Complete graph]]s need one more color than their maximum degree. They and the odd cycles are the only exceptions to 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 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.

For certain graphs, even fewer than Δ colors may be needed. Δ − 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

  • {{citation | last1 = Alon | first1 = Noga | author1-link = Noga Alon | last2 = Krivelevich | first2 = Michael | author2-link = Michael Krivelevich | last3 = Sudakov | first3 = Benny | author3-link = Benny Sudakov | doi = 10.1006/jctb.1999.1910 |doi-access=free | issue = 1 | journal = Journal of Combinatorial Theory | series = Series B | pages = 73–82 | title = Coloring graphs with sparse neighborhoods | volume = 77 | year = 1999}}
  • {{citation | last = Brooks | first = R. L. | authorlink = R. Leonard Brooks | journal = Mathematical Proceedings of the Cambridge Philosophical Society | pages = 194–197 | title = On colouring the nodes of a network | volume = 37 | doi = 10.1017/S030500410002168X | year = 1941| issue = 2 | bibcode = 1941PCPS...37..194B | s2cid = 209835194 }}.
  • {{citation | last1 = Grable | first1 = David A. | last2 = Panconesi | first2 = Alessandro | title = Fast distributed algorithms for Brooks–Vizing colourings | pages = 85–120 | volume = 37 | journal = Journal of Algorithms | doi = 10.1006/jagm.2000.1097 | year = 2000| s2cid = 14211416
  • {{citation | last1 = Hajnal | first1 = Péter | last2 = Szemerédi | first2 = Endre | author2-link = Endre Szemerédi | doi = 10.1137/0403008 | issue = 1 | journal = SIAM Journal on Discrete Mathematics | pages = 74–80 | title = Brooks coloring in parallel | volume = 3 | year = 1990}}.
  • {{citation | last = Karloff | first = H. J. | doi = 10.1016/0304-3975(89)90121-7 | issue = 1 | journal = Theoretical Computer Science | pages = 89–103 | title = An NC algorithm for Brooks' theorem | volume = 68 | year = 1989| doi-access =
  • {{citation | last = Lovász | first = L. | author-link = László Lovász | doi = 10.1016/0095-8956(75)90089-1 | journal = Journal of Combinatorial Theory | series = Series B | pages = 269–271 | title = Three short proofs in graph theory | volume = 19 | year = 1975| issue = 3 | doi-access = free
  • {{citation | last1 = Panconesi | first1 = Alessandro | last2 = Srinivasan | first2 = Aravind | doi = 10.1007/BF01200759 | issue = 2 | journal = Combinatorica | pages = 255–280 | title = The local nature of Δ-coloring and its algorithmic applications | volume = 15 | year = 1995| s2cid = 28307157
  • {{citation | doi = 10.1006/jctb.1998.1891 | last = Reed | first = Bruce | authorlink = Bruce Reed (mathematician) | issue = 2 | journal = Journal of Combinatorial Theory | series = Series B | pages = 136–149 | title = A strengthening of Brooks' theorem | volume = 76 | year = 1999| doi-access = free
  • {{citation | last = Skulrattanakulchai | first = San | doi = 10.1016/j.ipl.2005.12.007 | issue = 3 | journal = Information Processing Letters | pages = 101–106 | title = Δ-List vertex coloring in linear time | volume = 98 | year = 2006}}.
  • .

References

  1. {{harvtxt. Alon. Krivelevich. Sudakov. 1999.
  2. {{harvtxt. Skulrattanakulchai. 2006.
  3. {{harvtxt. Karloff. 1989; {{harvtxt. Hajnal. Szemerédi. 1990; {{harvtxt. Panconesi. Srinivasan. 1995; {{harvtxt. Grable. Panconesi. 2000.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

graph-coloringtheorems-in-graph-theory