Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-01-13T18:41:34.393Z Has data issue: false hasContentIssue false

2 - Brooks's theorem

Published online by Cambridge University Press:  05 May 2015

By
Michael Stiebitz  and
Bjarne Toft
Edited by
Lowell W. Beineke  and
Robin J. Wilson
Michael Stiebitz
Affiliation:
Technical University Ilmenau
Bjarne Toft
Affiliation:
University of London
Lowell W. Beineke
Affiliation:
Purdue University, Indiana
Robin J. Wilson
Affiliation:
The Open University, Milton Keynes
Get access

Summary

R. L. Brooks's seminal paper [4] of 1941 contains the first result – known as Brooks's theorem – on colouring abstract graphs. That it is worthwhile to study the chromatic number of graphs in general, rather than just planar graphs, was pointed out already by A. B. Kempe in 1879 in his paper [28] about mapcolouring. However, it was only with the paper by Brooks that vertex-colouring of abstract graphs became a topic of study. Over the years, this topic has developed into a rich theory and, as emphasized by B. Reed in his extensive paper [51], Brooks's theorem is just the tip of the iceberg.

Introduction

In this chapter only simple graphs are considered. Brooks's theorem relates the chromatic number to the maximum degree of a graph. In modern terminology Brooks's result is as follows:

Let G be a graph with maximum degree Δ, where Δ > 2, and suppose that no connected component of G is a complete graph KΔ+1. Then it is possible to colour the vertices of G with Δ colours so that no two vertices of the same colour are adjacent, and hence G has chromatic number at most Δ.

Brooks noticed that it suffices to prove the result for connected graphs, since the connected components of a graph can be coloured independently of each other. Furthermore, he observed that every graph with maximum degree Δ admits a (Δ+ 1)-colouring, by giving to each vertex in turn a colour different from all those colours already assigned to vertices to which it is adjacent. The three missing cases, where Δ = 0, 1, 2, can be easily included in Brooks's theorem. So another possible way of formulating Brooks's fundamental result is as follows.

Theorem 1.1 (Brooks's theorem) Let G be a connected graph of maximum degree Δ. Then χ(G) ≤ Δ+1, where equality holds if and only if G is a complete graph or an odd cycle.

Type
Chapter
Information
Topics in Chromatic Graph Theory , pp. 36 - 55
Publisher: Cambridge University Press
Print publication year: 2015

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. H. L., Abbott, D. R., Hare and B., Zhou, Sparse color-critical graphs and hypergraphs with no short cycles, J. Graph Theory 18 (1994), 373–388.Google Scholar
2. O. V., Borodin and A. V., Kostochka, On an upper bound of a graph's chromatic number, depending on the graph's degree and density, J. Combin. Theory (B) 23 (1977), 247–250.Google Scholar
3. O. V., Borodin, A. V., Kostochka, B., Lidiky and M., Yancey, Short proofs of coloring theorems on planar graphs, manuscript.
4. R. L., Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197.Google Scholar
5. R. L., Brooks, A procedure for dissecting a rectangle into squares, and an example for the rectangle whose sides are in the ratio 2:1, J. Combin. Theory (B) 8 (1970), 232–242.Google Scholar
6. R. L., Brooks, C. A. B., Smith, A. H., Stone and W. T., Tutte, The dissection of rectangles into squares, Duke Math. J. 7 (1940), 312–340.Google Scholar
7. R. L., Brooks, C. A. B., Smith, A. H., Stone and W. T., Tutte, A simple perfect square, Nederl. Akad. Wetensch. Proc. 50 (1947), 1300–1301.Google Scholar
8. R. L., Brooks, C. A. B., Smith, A. H., Stone and W. T., Tutte, Determinants and current flows in electric networks, Discrete Math. 100 (1992), 291–301.Google Scholar
9. P. A., Catlin, A bound on the chromatic number of a graph, Discrete Math. 22 (1978), 81–83.Google Scholar
10. P. A., Catlin, Brooks' graph-coloring theorem and the independence number, J. Combin. Theory (B) 27 (1979), 42–48.Google Scholar
11. B., Chen, K., Lih and P., Wu, Equitable coloring and the maximum degree, Europ. J. Combinatorics 15 (1994), 443–447.Google Scholar
12. D. W., Cranston and L., Rabern, Conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker, manuscript.
13. G. A., Dirac, The structure of k-chromatic graphs, Fund. Math. 40 (1953), 42–55.Google Scholar
14. G. A., Dirac, Map colour theorems related to the Heawood colour formula, J. London Math. Soc. 31 (1956), 460–471.Google Scholar
15. G. A., Dirac, A theorem of R. L. Brooks and a conjecture of H. Hadwiger, Proc. London Math. Soc. (3) 7 (1957), 161–195.Google Scholar
16. G. A., Dirac, The number of edges in critical graphs, J. Reine Angew. Math. 268/269 (1974), 150–164.Google Scholar
17. P., Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34–38.
18. P., Erdős, A. L., Rubin and H., Taylor, Choosability in graphs, Proc. West-Coast Conf. on Combinatorics, Graph Theory and Computing, Congr. Numer. XXVI (1979), 125–157.Google Scholar
19. B., Farzad, M., Molloy and B., Reed, (Δ – k)-critical graphs, Discrete Math. 93 (2005), 173–185.
20. T., Gallai, Kritische, Graphen I, II, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963), 165–192 and 373–395.
21. L., Gerencsér, Szinezési, problémákrol, Mat. Lapok 16 (1965), 274–277.
22. H., Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther Univ. Halle-Wittenberg, Math.-Nat. Reihe 8 (1958/59), 109–120.Google Scholar
23. A., Gyárfás, Problems from the world surrounding perfect graphs, Zastos. Mat. 19 (1988), 413–431.Google Scholar
24. A., Hajnal and E., Szeméredi, Proof of a conjecture ofP., Erdős, Combinatorial Theory and its Application, Vol. II (eds. P., Erdős et al.), North-Holland (1970), 601–623.Google Scholar
25. G., Hajos, Über eine Konstruktion nicht n-färbbarer Graphen, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturw. Reihe 10 (1961), 116–117.Google Scholar
26. T. R., Jensen and G. F., Royle, Small graphs with chromatic number 5: A computer search, J. Graph Theory 19 (1995), 107–116.Google Scholar
27. T. R., Jensen and B., Toft, Graph Coloring Problems, Wiley, 1995.Google Scholar
28. A. B., Kempe, On the geographical problem of four colours, Amer. J.Math. 2 (1879), 193–200.Google Scholar
29. H. A., Kierstead, A. V., Kostochka, A. V., Mydlarz and E., Szemeredi, A fast algorithm for equitable coloring, Combinatorica 30 (2010), 217–224.Google Scholar
30. A. V., Kostochka, Degree, density, and chromatic number (in Russian), Metody Diskret. Anal. 35 (1980), 45–70.Google Scholar
31. A. V., Kostochka, M., Stiebitz and B., Wirth, The colour theorems of Brooks and Gallai extended, Discrete Math. 191 (1996), 125–137.Google Scholar
32. A. V., Kostochka and M., Stiebitz, Excess in colour-critical graphs, Graph Theory and Com-binatorial Biology (Balatonlelle, Hungary, 1996), Bolyai Society Mathematical Studies 7 (1999), 87–99.Google Scholar
33. A. V., Kostochka and M., Stiebitz, On the number of edges in colour-critical graphs and hypergraphs, Combinatorica 20 (2000), 521–530.Google Scholar
34. A. V., Kostochka and M., Stiebitz, A list version of Dirac's theorem on the number of edges in colour-critical graphs, J. Graph Theory 39 (2002), 165–167.Google Scholar
35. A. V., Kostochka and M., Stiebitz, A new lower bound for the number of edges in colour-critical graphs and hypergraphs, J. Combin. Theory (B) 20 (2003), 374–402.Google Scholar
36. A. V., Kostochka and M., Yancey, Ore's conjecture on color-critical graphs is almost true, manuscript.
37. A. V., Kostochka and M., Yancey, Ore's conjecture for k = 4 and Grotzsch's theorem, Combinatorica 34 (2014), 323–329.Google Scholar
38. A. V., Kostochka and M., Yancey, A Brooks-type result for sparse critical graphs, manuscript.
39. M., Krivelevich, On the minimal number of edges in color-critical graphs, Combinatorica 17 (1997), 401–426.Google Scholar
40. H. V., Kronk and A. T., White, A 4-color theorem for toroidal graphs, Proc. Amer. Math. Soc. 34 (1972), 83–86.Google Scholar
41. J., Lawrence, Covering the vertex set of a graph with subgraphs of smaller degree, Discrete Math. 21 (1978), 61–88.Google Scholar
42. L., Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966), 237–238.Google Scholar
43. L. S., Melnikov and V. G., Vizing, New proof of Brooks' theorem, J. Combin. Theory 7 (1969), 289–290.Google Scholar
44. P., Mihok, An extension of Brooks' theorem, Ann. Discrete Math. 51 (1992), 235–236.Google Scholar
45. J., Mitchem, A short proof of Catlin's extension of Brooks' theorem, Discrete Math. 21 (1978), 213–214.Google Scholar
46. M., Molloy, Chromatic neighborhood sets, J. Graph Theory 31 (1999), 303–311.Google Scholar
47. M., Molloy and B., Reed, Colouring graphs when the number of colours is almost the maximum degree, Proceedings ofthe 33rd Annual ACM Symposium on Theory of Computing (2001), 462–470.Google Scholar
48. M., Molloy and B., Reed, Graph Coloring and the Probabilistic Method, Springer, 2002.Google Scholar
49. L., Lovász, Three short proofs in graph theory, J. Graph Theory 19 (1975), 269–271.Google Scholar
50. O., Ore, The Four Colour Problem, Academic Press, 1967.Google Scholar
51. B., Reed, χ, Δ,and ω, J. Graph Theory 27 (1998), 177–213.
52. B., Reed, A strengthening of Brooks's theorem, J. Combin. Theory (B) 76 (1999), 136–149.Google Scholar
53. G. F., Royle, Small graphs, http://school.maths.uwa.edu.au/~gordon/remote/graphs/, 2000.
54. M., Stehlík, Critical graphs with connected complements, J. Combin. Theory (B) 89 (2003), 189–194.Google Scholar
55. M., Stiebitz, Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs, Combinatorica 2 (1982), 315–323.Google Scholar
56. C., Thomassen, Grötzsch's 3-colour theorem and its counterparts for the torus and the projective plane, J. Combin. Theory (B) 62 (1994), 268–279.
57. C., Thomassen, Color-critical graphs on a fixed surface, J. Combin. Theory (B) 70 (1997), 67–100.Google Scholar
58. B., Toft, Colour-critical graphs and hypergraphs, J. Combin. Theory (B) 16 (1974), 145–161.Google Scholar
59. B., Toft, Critical subgraphs of colour critical graphs, Discrete Math. 7 (1974), 377–392.Google Scholar
60. H., Tverberg, On Brooks' theorem and some related results, Math. Scand. 52 (1983), 37–40.Google Scholar
61. J., Weinstein, Excess in critical graphs, J. Combin. Theory (B) 18 (1975), 24–31.Google Scholar
62. A. A., Zykov, On some properties of linear complexes (in Russian), Mat. Sbornik N. S. 24 (1949), 163–188; English translation in Amer. Math. Soc. Transl. 79 (1952), 418–449.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×