
In
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, Brooks' theorem states a relationship between the maximum
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathemati ...
of a graph and its
chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
. 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, though it has taken on a special meaning in South ...
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 ...
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 undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
''G'' with maximum
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathemati ...
Δ,
the
chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
of ''G'' is at most Δ, unless ''G'' is a complete graph or an odd cycle, in which case the chromatic number is Δ + 1.
Proof
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 a ...
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
The term regular can mean normal or in accordance with rules. It may refer to:
People
* Moses Regular (born 1971), America football player
Arts, entertainment, and media Music
* "Regular" (Badfinger song)
* Regular tunings of stringed instrum ...
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: given any connected undirected graph with maximum degree Δ that is neither a
clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popula ...
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 . 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. shows that Δ − 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 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 de ...
, 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, an 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, blue ...
, 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 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 clas ...
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