Brooks’ Theorem
   HOME

TheInfoList



OR:

In
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, Brooks' theorem states a relationship between the maximum degree of a graph and its
chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be
colored ''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow era to refer to an African American. In many places, it may be considered a slur. Dictionary definitions The word ''colored'' wa ...
with only Δ colors, except for two cases,
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
s and
cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
s 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 Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...
undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
''G'' with maximum degree Δ, the
chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
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 László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He ...
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 In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence an ...
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 Regular may refer to: Arts, entertainment, and media Music * "Regular" (Badfinger song) * Regular tunings of stringed instruments, tunings with equal intervals between the paired notes of successive open strings Other uses * Regular character, ...
graphs with Δ ≥ 3. In this case, Lovász shows that one can find a
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...
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 In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and T ...
: given any connected undirected graph with maximum degree Δ that is neither a
clique A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...
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 graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...
s, or more generally graphs in which the
neighborhood A neighbourhood (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neigh ...
of every vertex is sufficiently
sparse Sparse is a computer software tool designed to find possible coding faults in the Linux kernel. Unlike other such tools, this static analysis tool was initially designed to only flag constructs that were likely to be of interest to kernel deve ...
, O(Δ/log Δ) colors suffice. The degree of a graph also appears in upper bounds for other types of coloring; for
edge coloring In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red ...
, the result that the chromatic index is at most Δ + 1 is
Vizing's theorem In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree of the graph. At least colors are always necessary, so the undirected gr ...
. An extension of Brooks' theorem to
total coloring In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be ''proper'' in the sense that no adjacent edges, no adjacent vertices ...
, stating that the total chromatic number is at most Δ + 2, has been conjectured by
Mehdi Behzad Mehdi Behzad (Persian:مهدی بهزاد; born April 22, 1936) is an Iranian mathematician specializing in graph theory. He introduced his total coloring theory (also known as "Behzad's conjecture" or "the total chromatic number conjecture") dur ...
and Vizing. The Hajnal–Szemerédi theorem on
equitable coloring In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that *No two adjacent vertices have the same color, and *The numbers of vertices in any two color class ...
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