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-cphqk Total loading time: 0 Render date: 2025-01-13T18:45:17.202Z Has data issue: false hasContentIssue false

1 - Colouring graphs on surfaces

Published online by Cambridge University Press:  05 May 2015

By
Bojan Mohar
Edited by
Lowell W. Beineke  and
Robin J. Wilson
Bojan Mohar
Affiliation:
University of Ljubljana
Lowell W. Beineke
Affiliation:
Purdue University, Indiana
Robin J. Wilson
Affiliation:
The Open University, Milton Keynes
Get access

Summary

Developments in graph colouring theory were motivated by the four-colour problem and Heawood's theorem. Both of these were originally formulated as map-colouring problems that can be expressed as colouring graphs embedded on surfaces. This chapter gives an overview of the abundance of results concerning the chromatic number of graphs that are embedded on surfaces.

Introduction

In 1852 Francis Guthrie asked whether the regions of every planar map can be coloured with four colours in such a way that no two regions of the map with common boundary receive the same colour. In effect, by duality Guthrie was asking whether every planar graph is 4-colourable. This easily stated problem became known as the famous four-colour problem. Attempts to solve it led to many important results in graph theory, but the problem itself remained unsolved for more than a century. It was finally answered in the positive by Appel and Haken [9], [10], [12]. More about its proof comes later in this chapter.

For more than a century, the four-colour problem was one of the driving forces that led to developments in graph theory, and specifically graph colouring theory. Its generalization – the Heawood problem – was the main motivation for developments in topological graph theory (see [51] or [49]). Both of these were originally formulated as map-colouring problems, asking about colouring the faces of an embedded graph so that adjacent faces receive different colours. Every map-colouring problem can be expressed as a graph-colouring problem by considering the dual graph of the map. Its vertices correspond to the faces of the map, and two vertices are adjacent if the corresponding faces are adjacent on the surface.

In this chapter we discuss the colouring of graphs embedded on surfaces. We start by describing some of the ideas in the proof of the four-colour theorem and give a proof of the list-colouring version of the five-colour theorem that is due to Thomassen.

Type
Chapter
Information
Topics in Chromatic Graph Theory , pp. 13 - 35
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. M. O., Albertson, Open problem 2, The Theory and Applications of Graphs (ed. G., Chartrand et al.), Wiley (1981), 609.Google Scholar
2. M. O., Albertson, You can't paint yourself into a corner, J. Combin. Theory (B) 73 (1998), 189–194.Google Scholar
3. M. O., Albertson, G. G., Chappell, H. A., Kierstead, A., Kündgen and R., Ramamurthi, Coloring with no 2-colored P4's, Electron. J. Combin. 11 (2004), 13 pp.Google Scholar
4. M. O., Albertson and J. P., Hutchinson, The three excluded cases of Dirac's map-color theorem, Ann. N. Y. Acad. Sci. 319 (1979), 7–17.Google Scholar
5. M. O., Albertson and J. P., Hutchinson, On 6-chromatic triangulations, Proc. London Math. Soc. 41 (1980), 533–556.Google Scholar
6. N., Alon, B., Mohar and D. P., Sanders, On acyclic colorings of graphs on surfaces, Israel J. Math. 94 (1996), 273–283.Google Scholar
7. N., Alon and M., Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), 125–134.Google Scholar
8. A., Altschuler, Hamiltonian circuits in some maps on the torus, Discrete Math. 1 (1972), 299–314.Google Scholar
9. K., Appel and W., Haken, The existence of unavoidable sets of geographically good configurations, Illinois J. Math. 20 (1976), 218–297.Google Scholar
10. K., Appel and W., Haken, Every planar map is four colorable. Part I: Discharging, Illinois J. Math. 21 (1977), 429–490.Google Scholar
11. K., Appel and W., Haken, Every Planar Map is Four Colorable, Contemp. Math. 98, Amer. Math. Soc., 1989.
12. K., Appel, W., Haken and J., Koch, Every planar map is four colorable. Part II: Reducibility, Illinois J. Math. 21 (1977), 491–567.Google Scholar
13. T., Böhme, B., Mohar and M., Stiebitz, Dirac's map-color theorem for choosability, J. Graph Theory 32 (1999), 327–339.Google Scholar
14. O. V., Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979), 211–236.Google Scholar
15. O. V., Borodin, M., Chen, A. O., Ivanova and A., Raspaud, Acyclic 3-choosability of sparse graphs with girth at least 7, Discrete Math. 310 (2010), 2426–2434.Google Scholar
16. O. V., Borodin, D. G., Fon-Der-Flaass, A. V., Kostochka, A., Raspaud and E., Sopena, Acyclic list 7-coloring of planar graphs, J. Graph Theory 40 (2002), 83–90.Google Scholar
17. O. V., Borodin and A. O., Ivanova, Acyclic 5-choosability of planar graphs without 4-cycles (in Russian), Sibirsk. Mat. Zh. 52 (2011), 522–541.Google Scholar
18. N., Chenette, L., Postle, N., Streib, R., Thomas and C., Yerger, Five-coloring graphs in the Klein bottle, J. Combin. Theory (B) 102 (2012), 1067–1098.Google Scholar
19. M., DeVos, L., Goddyn, B., Mohar, D., Vertigan and X., Zhu, Coloring-flow duality of embedded graphs, Trans. Amer. Math. Soc. 357 (2005), 3993–4016.Google Scholar
20. M., DeVos, K., Kawarabayashi and B., Mohar, Locally planar graphs are 5-choosable, J. Combin. Theory (B) 98 (2008), 1215–1232.Google Scholar
21. G. A., Dirac, Map colour theorems, Canad. J. Math. 4 (1952), 480–490.Google Scholar
22. G. A., Dirac, Short proof of the map colour theorem, Canad. J. Math. 9 (1957), 225–226.Google Scholar
23. G. A., Dirac, A, theorem of R. L., Brooks and a conjecture of H., Hadwiger, Proc. London Math. Soc. (3) 7 (1957), 161–195.
24. G. A., Dirac, Map colour theorems related to the Heawood colour formula, J. London Math. Soc. 32 (1957), 436–455.Google Scholar
25. Z., Dvořák, D., Král' and R., Thomas, Coloring triangle-free graphs on surfaces, Proc. 20th Ann. ACM-SIAM Symp. on Discrete Algorithms, SODA 2009, SIAM (2009), 120–129.Google Scholar
26. Z., Dvořák, D., Král' and R., Thomas, Coloring planar graphs with triangles far apart, http://arxiv.org/abs/0911.0885.
27. Z., Dvořák, B., Lidický and B., Mohar, 5-choosability of graphs with crossings far apart, http://arxiv.org/abs/1201.3014.
28. Z., Dvořák, B., Lidický, B., Mohar and L., Postle, 5-list-coloring planar graphs with distant precolored vertices, http://arxiv.org/abs/1209.0366.
29. K., Edwards, The complexity of some graph colouring problems, Discrete Appl. Math. 36 (1992), 131–140.Google Scholar
30. P., Erdős, Graph theory and probability, II, Canad. J. Math. 13 (1961), 346–352.Google Scholar
31. P., Erdős, A. L., Rubin and H., Taylor, Choosability in graphs, Proc. West Coast Conference on Combinatorics, Graph Theory and Computing (Arcata, California), Congr. Numer. 26 (1980), 125–157.Google Scholar
32. S., Fisk, The non-existence of colorings, J. Combin. Theory (B) 24 (1978), 247–248.Google Scholar
33. S., Fisk and B., Mohar, Coloring graphs without short non-bounding cycles, J. Combin. Theory (B) 60 (1994), 268–276.Google Scholar
34. J., Gimbel and C., Thomassen, Coloring graphs with fixed genus and girth, Trans. Amer. Math. Soc. 349 (1997), 4555–4564.Google Scholar
35. H., Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss.Z.Martin Luther-Univ. Halle Wittenberg, Math.-Nat. Reihe 8 (1959), 109–120.Google Scholar
36. P. J., Heawood, Map-colour theorem, Quart. J. Pure Appl. Math. 24 (1890), 332–338.Google Scholar
37. J. P., Hutchinson, Three-coloring graphs embedded on surfaces with all faces even-sided, J. Combin. Theory (B) 65 (1995), 139–155.Google Scholar
38. J., Hutchinson, R. B., Richter and P., Seymour, Colouring Eulerian triangulations, J. Combin. Theory (B) 84 (2002), 225–239.Google Scholar
39. K., Kawarabayashi, D., Král, J., Kynčl and B., Lidický, 6-critical graphs on the Klein bottle, SIAM J. Discrete Math. 23 (2009), 372–383.Google Scholar
40. K., Kawarabayashi and B., Mohar, List-color-critical graphs on a fixed surface, Proc. Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09),SIAM (2009), 1156–1165.Google Scholar
41. K.-I., Kawarabayashi and B., Mohar, Star coloring and acyclic coloring of locally planar graphs, SIAM J. Discrete Math. 24 (2010), 56–71.Google Scholar
42. H. A., Kierstead, A., Kúndgen and C., Timmons, Star coloring bipartite planar graphs, J. Graph Theory 60 (2009), 1–10.Google Scholar
43. H., Kierstead, B., Mohar, S., Šrpacapan, D., Yang and X., Zhu, The two-coloring number and degenerate colorings of planar graphs, SIAM J. Discrete Math. 23 (2009), 1548–1560.Google Scholar
44. S., Klavžrar and B., Mohar, The chromatic numbers of graph bundles over cycles, Discrete Math. 138 (1995), 301–314.Google Scholar
45. D., Král' and R., Skrekovski, The last excluded case of Dirac's map-color theorem for choosability, J. Graph Theory 51 (2006), 319–354.Google Scholar
46. M., Mirzakhani, A small non-4-choosable planar graph, Bull. Inst. Combin. Appl. 17 (1996), 15–18.Google Scholar
47. B., Mohar and P. D., Seymour, Coloring locally bipartite graphs on surfaces, J. Combin. Theory (B) 84 (2002), 301–310.Google Scholar
48. B., Mohar and S., Šrpacapan, Degenerate and star colorings of graphs on surfaces, Europ. J. Combin. 33 (2012), 340–349.Google Scholar
49. B., Mohar and C., Thomassen, Graphs on Surfaces, Johns Hopkins University Press, 2001.Google Scholar
50. M., Montassier, Acyclic 4-choosability of planar graphs with girth at least 5, Graph Theory in Paris (ed. A., Bondy et al.), Birkhauser (2007), 299–310.Google Scholar
51. G., Ringel, Map Color Theorem, Springer-Verlag, 1974.Google Scholar
52. G., Ringel and J. W. T., Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968), 438–445.Google Scholar
53. N., Robertson, D. P., Sanders, P., Seymour and R., Thomas, Efficiently four-coloring planar graphs, Proc. Assoc. Comp. Mach. Symp. Theory Comput. 28 (1996), 571–575.Google Scholar
54. N., Robertson, D., Sanders, P., Seymour and R., Thomas, The four-colour theorem, J. Combin. Theory (B) 70 (1997), 2–44.Google Scholar
55. R., Šrkrekovski, A theorem on map colorings, Bull. Inst. Combin. Appl. 35 (2002), 53–60.Google Scholar
56. C., Timmons, Star coloring high girth planar graphs, Electron. J. Combin. 15 (2008), Research Paper 124.Google Scholar
57. R., Thomas, http://people.math.gatech.edu/thomas/FC/fourcolor.html
58. C., Thomassen, Five-coloring maps on surfaces, J. Combin. Theory (B) 59 (1993), 89–105.Google Scholar
59. C., Thomassen, Every planar graph is 5-choosable, J Combin Theory (B) 62 (1994), 180–181.Google Scholar
60. C., Thomassen, Five-coloring graphs on the torus, J Combin Theory (B) 62 (1994), 11–33.Google Scholar
61. C., Thomassen, 3-list coloring planar graphs of girth 5, J Combin Theory (B) 64 (1995), 101–107.Google Scholar
62. C., Thomassen, Color-critical graphs on a fixed surface, J. Combin. Theory (B) 70 (1997), 67–100.Google Scholar
63. C., Thomassen, The chromatic number of a graph of girth 5 on a fixed surface, J. Combin. Theory(B) 87 (2003), 38–71.Google Scholar
64. W. T., Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 80–91.Google Scholar
65. M., Voigt, List colourings of planar graphs, Discrete Math. 120 (1993), 215–219.Google Scholar
66. M., Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math. 146 (1995), 325–328.Google Scholar
67. M., Voigt and B., Wirth, On 3-colorable non-4-choosable planar graphs, J. Graph Theory 24 (1997), 233–235.Google Scholar
68. R., Wilson, Four Colors Suffice (revised color edition), Princeton Science Series, Princeton University Press, 2014.Google Scholar
69. D. A., Youngs, 4-chromatic projective graphs, J. Graph Theory 21 (1996), 219–227.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
×