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.
Video Brooks' theorem
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.
Maps Brooks' theorem
Proof
László Lovász (1975) 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. 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. This has been proved by Vadim Vizing (1976).
For certain graphs, even fewer than ? colors may be needed. Bruce Reed (1999) shows that ? - 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
- 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
- Brooks, R. L. (1941), "On colouring the nodes of a network", Mathematical Proceedings of the Cambridge Philosophical Society, 37: 194-197, doi:10.1017/S030500410002168X .
- Grable, David A.; Panconesi, Alessandro (2000), "Fast distributed algorithms for Brooks-Vizing colourings", Journal of Algorithms, 37: 85-120, doi:10.1006/jagm.2000.1097 .
- Hajnal, Péter; Szemerédi, Endre (1990), "Brooks coloring in parallel", SIAM Journal on Discrete Mathematics, 3 (1): 74-80, doi:10.1137/0403008 .
- 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 .
- Lovász, L. (1975), "Three short proofs in graph theory", Journal of Combinatorial Theory, Series B, 19: 269-271, doi:10.1016/0095-8956(75)90089-1 .
- Panconesi, Alessandro; Srinivasan, Aravind (1995), "The local nature of ?-coloring and its algorithmic applications", Combinatorica, 15 (2): 255-280, doi:10.1007/BF01200759 .
- Reed, Bruce (1999), "A strengthening of Brooks' theorem", Journal of Combinatorial Theory, Series B, 76 (2): 136-149, doi:10.1006/jctb.1998.1891 .
- Skulrattanakulchai, San (2006), "?-List vertex coloring in linear time", Information Processing Letters, 98 (3): 101-106, doi:10.1016/j.ipl.2005.12.007 .
- Vizing, V. G. (1976), "Vertex colorings with given colors", Diskret. Analiz. (in Russian), 29: 3-10 .
External links
- Weisstein, Eric W. "Brooks' Theorem". MathWorld.
Source of the article : Wikipedia
0 Comments