Colouring graphs on surfaces

doi:10.1017/CBO9781139519793.004

1 - Colouring graphs on surfaces

Published online by Cambridge University Press: 05 May 2015

Bojan Mohar

Edited by

Lowell W. Beineke and

Robin J. Wilson

Show author details

Bojan Mohar: Affiliation:
University of Ljubljana
Lowell W. Beineke: Affiliation:
Purdue University, Indiana
Robin J. Wilson: Affiliation:
The Open University, Milton Keynes

Book contents

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

DOI: https://doi.org/10.1017/CBO9781139519793.004 [Opens in a new window]

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

Book contents

1 - Colouring graphs on surfaces

Summary

Access options

References

Save book to Kindle

Save book to Dropbox

Save book to Google Drive