Brooks’ theorem
Encyclopedia
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 graph in which every vertex has at most Δ neighbors, the vertices may be colored
with only Δ colors, except for two cases, complete graph
s and cycle graph
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.
Δ,
the chromatic number of G is at most Δ unless G is a clique or an odd cycle, in which case the chromatic number is Δ + 1.
, 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.
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
in 1976.
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
s, 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 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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, Brooks' theorem states a relationship between the maximum degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
of a graph and its chromatic number. According to the theorem, in a graph in which every vertex has at most Δ neighbors, the vertices may be colored
Graph coloring
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 of a graph such that no two adjacent vertices share the...
with only Δ colors, except for two cases, complete graph
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.-Properties:...
s and cycle graph
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 connected in a closed chain. The cycle graph with n vertices is called Cn...
s of odd length, which require Δ + 1 colors.
The theorem is named after R. Leonard Brooks
R. Leonard Brooks
Rowland Leonard Brooks was an English mathematician, known for proving Brooks' theorem on the relation between the chromatic number and the degree of graphs. He studied at Trinity College, Cambridge University, and also worked with fellow Trinity students W. T...
, 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 degreeDegree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
Δ,
the chromatic number of G is at most Δ unless G is a clique 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 biconnectedBiconnected graph
In the mathematical discipline of graph theory, a biconnected graph is a connected graph with no articulation vertices.In other words, a biconnected graph is connected and nonseparable, meaning that if any vertex were to be removed, the graph will remain connected.The property of being 2-connected...
, 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
Greedy coloring
In the study of graph coloring problems in mathematics and computer science, a greedy coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color...
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
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
graphs with Δ ≥ 3. In this case, Lovász shows that one can find a spanning tree
Spanning tree
Spanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
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 cliqueClique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
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
Vadim G. Vizing
Vadim Georgievich Vizing is a Ukrainian mathematician known for his contributions to graph theory, and especially for Vizing's theorem stating that the edges of any graph with maximum degree Δ can be colored with at most Δ + 1 colors.- Biography :Vizing was born in Kiev on March...
in 1976.
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
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 girth ≥ 4, graphs with no induced 3-cycle, or locally...
s, 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
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 adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
, the result that the chromatic index is at most Δ + 1 is Vizing's theorem. An extension of Brooks' theorem to total coloring
Total coloring
In graph theory, total coloring is a type of 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 vertices, no adjacent edges, and no edge and its endvertices are assigned the same color.The...
, stating that the total chromatic number is at most Δ + 2, has been conjectured by Behzad and Vizing. The Hajnal–Szemerédi theorem on equitable coloring
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...
states that any graph has a (Δ + 1)-coloring in which the sizes of any two color classes differ by at most one.