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-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-05T02:33:08.318Z Has data issue: false hasContentIssue false

15 - Unsolved graph colouring problems

Published online by Cambridge University Press:  05 May 2015

By
Tommy Jensen  and
Bjarne Toft
Edited by
Lowell W. Beineke  and
Robin J. Wilson
Tommy Jensen
Affiliation:
University of Southern Denmark
Bjarne Toft
Affiliation:
University of Southern Denmark
Lowell W. Beineke
Affiliation:
Purdue University, Indiana
Robin J. Wilson
Affiliation:
The Open University, Milton Keynes
Get access

Summary

Our book Graph Coloring Problems [85] appeared in 1995. It contains descriptions of unsolved problems, organized into sixteen chapters. A large number of publications on graph colouring have appeared since then, and in particular around thirty of the 211 problems in that book have been solved. In this chapter we review some of our favourite problems that remain unsolved.

Introduction

A main reason for the continued interest in the area of graph colouring is its wealth of interesting unsolved problems. Many of these are easy to state, but seemingly difficult to solve. However they are not impossible, as the literature in the field will testify.

The seven most striking results of the past twenty years are:

  1. • the 5-list-colourability of planar graphs (dating back to V. G. Vizing in 1975 and to P. Erdős, A. L. Rubin and H. Taylor in 1979) by Thomassen [159]

  2. • the confirmation by Robertson, Sanders, Seymour and Thomas [137] of the truth of the four-colour theorem (F. Guthrie and A. De Morgan (1852))

  3. • the asymptotic solution by Reed [134] of the problem as to whether for k ≥ 9 there are k-chromatic graphs without complete k-graphs and of maximum degree k (V. G. Vizing (1968) and O. V. Borodin and A. V. Kostochka (1977))

  4. • the proof by Chudnovsky, Robertson, Seymour and Thomas [39] of the strong perfect graph conjecture of C. Berge around 1960

  5. • the proof by Thomassen [161] of the weak 3-flow conjecture of W. T. Tutte (1954) and F. Jaeger (1988)

  6. • the solution by Kostochka and Yancey [111] to the problem of critical graphs with few edges (due to T. Gallai (1963) and O. Ore (1967))

  7. • the description found by Borodin, Dvořák, Kostochka, Lidický and Yancey [24] of all 4-critical planar graphs with exactly four triangles (B. Grünbaum (1963), V. A. Aksenov (1974) and P. Erdős (1990)).

In addition to these major achievements there are many other important results – in fact, thirty-one of the original 211 problems from the lists in Jensen and Toft [85] were solved by 2013.

Type
Chapter
Information
Topics in Chromatic Graph Theory , pp. 327 - 357
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 and B., Zhou, On small faces in 4-critical planar graphs, Ars Combin. 32 (1991), 203–207.Google Scholar
2. M., Aigner and S., Brandt, Embedding arbitrary graphs of maximum degree two, J. London Math. Soc. 48 (1993), 39–51.Google Scholar
3. V. A., Aksionov and L. S., Melnikov, Essay on the theme: the three-color problem, Combinatorics (eds. A., Hajnal and V. T., Sós), Colloq. Math. Soc. Janos Bolyai 18, North-Holland (1978), 23–34.Google Scholar
4. B., Albar and D., Gonçalves, On triangles in Kr-minor free graphs, arXiv:1304.5468v1, 2013.
5. M. O., Albertson, Open problem 2, Theory and Applications of Graphs (eds. G., Chartrand et al.), Wiley (1981), 609.Google Scholar
6. M. O., Albertson, D. L., Boutin and E., Gethner, The thickness and chromatic number of r-inflated graphs, Discrete Math. 310 (2010), 2725–2734.Google Scholar
7. M. O., Albertson, D. L., Boutin and E., Gethner, More results on r-inflated graphs: Arboricity, thickness, chromatic number and fractional chromatic number, Ars Math. Contemp. 4 (2011), 5–24.Google Scholar
8. R. E. L., Aldred, S., Bau, D. A., Holton and B. D., McKay, Nonhamiltonian 3-connected cubic planar graphs, SIAM J. Discrete Math. 13 (2000), 25–32.Google Scholar
9. L. D., Andersen, On edge-colourings of graphs, Math. Scand. 40 (1977), 161–175.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, W., Haken and J., Koch, Every planar map is four colorable, Part II: Reducibility, Illinois J. Math. 21 (1977), 491–567.Google Scholar
12. J., Balogh, A. V., Kostochka, N., Prince and M., Stiebitz, The Erdős-Lovász Tihany conjecture for quasi-line graphs, Discrete Math. 309 (2012), 3985–3991.Google Scholar
13. J., Barát, G., Joret and D. R., Wood, Disproof of the list Hadwiger conjecture, Electron. J. Combin. 18 (2011), 232.Google Scholar
14. D., Barnette, Conjecture 5, Recent Progress in Combinatorics (ed. W. T., Tutte), Proc. Third Waterloo Conference on Combinatorics, May 1968, Academic Press (1969), 343.Google Scholar
15. T., Bartnicki, J., Grytczuk, H. A., Kierstead and X., Zhu, The map-coloring game, Amer. Math. Monthly 114 (2007), 793–803.Google Scholar
16. J., Beck, Combinatorial Games, Encyclopedia of Mathematics and its Applications 114, Cambridge University Press, 2008; paperback edn., 2011.Google Scholar
17. M., Behzad, Graphs and Their Chromatic Numbers, Ph.D. thesis, Michigan State University, 1965.Google Scholar
18. A., Bernhart, Six rings in minimal five color maps, Amer. J. Math. 69 (1947), 391–H2.Google Scholar
19. H.-G., Bigalke, Heinrich Heesch, Kristallgeometrie, Parkettierungen, Vierfarben-forschung, Birkhäuser Verlag (1988), 155.Google Scholar
20. B., Bollobás and S. E., Eldridge, Problem, Proc. Fifth British Combinatorial Conference (Aberdeen, 1975) (eds. C. St. J. A., Nash-Williams and J., Sheehan), Utilitas Math. (1976), 690.
21. B., Bollobás and S. E., Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory (B) 25 (1978), 105–124.Google Scholar
22. B., Bollobás and A. J., Harris, List-colourings of graphs, Graphs Combin. 1 (1985), 115–127.Google Scholar
23. O. V., Borodin, Colorings of plane graphs: a survey, Discrete Math. 313 (2013), 517–539.Google Scholar
24. O. V., Borodin, Z., Dvořák, A. V., Kostochka, B., Lidický and M. P., Yancey, Planar 4-critical graphs with four triangles, Europ. J. Combin. 41 (2014), 138–151.Google Scholar
25. O. V., Borodin, A. N., Glebov, T. R., Jensen and A., Raspaud, Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable, Sib. Elektron. Mat. Izv. 3 (2006), 428–440.Google Scholar
26. O. V., Borodin, A. N., Glebov, M., Montassier and A., Raspaud, Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable, J. Combin. Theory (B) 99 (2009), 668–673.Google Scholar
27. O. V., Borodin, A. N., Glebov, A., Raspaud and M. R., Salavatipour, Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. Combin. Theory (B) 93 (2005), 303–311.Google Scholar
28. O. V., Borodin, A. V., Kostochka and D. R., Woodall, List edge and list total colourings of multigraphs, J. Combin. Theory (B) 71 (1997), 184–204.Google Scholar
29. M., Borowiecki, Research problem 172, Discrete Math. 121 (1993), 235–236.Google Scholar
30. D. L., Boutin, E., Gethner and T., Sulanke, Thickness-two graphs, part one: new nine-critical graphs, permuted layer graphs, and Catlin's graphs, J. Graph Theory 57 (2008), 198–214.Google Scholar
31. G., Brinkmann, B. D., McKay and U., von Nathusius, Backtrack search and look-ahead for the construction of planar cubic graphs with restricted face sizes, MATCH Commun. Math. Comput. Chem. 48 (2003), 163–177.Google Scholar
32. G., Brinkmann, B. D., McKay and C., Saager, The smallest cubic graphs of girth nine, Combin. Probab. Comput. 5 (1995), 1–13.Google Scholar
33. H., Broersma, P. A., Golovach, D., Paulusma and J., Song, Updating the complexity status of coloring graphs without a fixed induced linear forest, Theoret. Comput. Sci. 414 (2012), 9–19.Google Scholar
34. R. L., Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1941), 194–197.Google Scholar
35. P. A., Catlin, Embedding Subgraphs and Coloring Graphs under Extremal Degree Conditions, Ph.D. thesis, Ohio State University, 1976.Google Scholar
36. P. A., Catlin, Embedding subgraphs under extremal degree conditions. Proc. 8th South-Eastern Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, 1977), Congr. Numer. 19 (1977), 139–145.Google Scholar
37. A. G., Chetwynd and R., Häggkvist, A note on list colourings, J. Graph Theory 13 (1989), 87–95.Google Scholar
38. M., Chudnovsky, A. D., King, M., Plumettaz and P. D., Seymour, A local strengthening of Reed's omega, Delta, chi conjecture for quasi-line graphs, SIAM J. Discrete Math. 27 (2013), 95–108.Google Scholar
39. M., Chudnovsky, N., Robertson, P. D., Seymour and R., Thomas, The strong perfect graph theorem, Ann. of Math. (2) 164 (2006), 51–229.Google Scholar
40. M., Chudnovsky and P. D., Seymour, Extending the Gyárfás-Sumner conjecture, J. Combin. Theory (B) 105 (2014), 11–16.Google Scholar
41. B., Csaba, A., Shokoufandeh and E., Szemerédi, Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three, Combinatorica 23 (2003), 35–72.Google Scholar
42. M., DeVos, K., Kawarabayashi and B., Mohar, Locally planar graphs are 5-choosable, J. Combin. Theory (B) 98 (2008), 1215–1232.Google Scholar
43. G. A., Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc. 27 (1952), 85–92.Google Scholar
44. A. A., Dobrynin, L. S., Melnikov and A. V., Pyatkin, Regular 4-critical graphs of even degree, J. Graph Theory 46 (2004), 103–130.Google Scholar
45. A. A., Dobrynin, L. S., Melnikov and A. V., Pyatkin, Erdős regular graphs of even degree, Discuss. Math. Graph Theory 27 (2007), 269–279.Google Scholar
46. P., Duchet and H., Meyniel, On Hadwiger's number and the stability number, Graph Theory (ed. B., Bollobás), Annals of Discrete Mathematics, North-Holland (1982), 71–73.Google Scholar
47. K., Edwards and A. D., King, A superlocal version of Reed's conjecture, arXiv:1208.5188, 2012.Google Scholar
48. P., Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34–38.Google Scholar
49. P., Erdős, A. I., 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
50. P., Erdős, On some aspects of my work with Gabriel Dirac, Graph Theory in Memory of G. A. Dirac (eds. L. D., Andersen et al.), Annals of Discrete Mathematics 41, North-Holland (1989), 111–116.Google Scholar
51. L., Esperet, M., Montassier and X., Zhu, Adapted list coloring of planar graphs, J. Graph Theory 62 (2009), 127–138.Google Scholar
52. S., Fadnavis, A generalization of the birthday problem and the chromatic polynomial, arXiv:1105.0698v2, 2011.Google Scholar
53. G., Fan and A., Raspaud, Fulkerson's conjecture and circuit covers, J. Combin. Theory (B) 61 (1994), 133–138.Google Scholar
54. T., Feder and C., Subi, On Barnette's conjecture, Electron. Colloq. Comput. Complexity 15 (2006).Google Scholar
55. U., Feige, E., Ofek and U., Wieder, Approximating Maximum Edge Coloring in Multi- graphs, Lecture Notes in Comput. Sci. 2462 (2002), 108–121.
56. J. L., Fouquet and J. M., Vanherpe, On the perfect matching index of bridgeless cubic graphs, arXiv:0904.1296, 2009.Google Scholar
57. O., Frink, A proof of Petersen's theorem, Ann. Math. 27 (1926), 491–493.Google Scholar
58. R., Fritsch and G., Fritsch, The Four Color Theorem: History, Topological Foundations and Idea of Proof, Springer, 1998.Google Scholar
59. D. R., Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Program. 1 (1971), 168–194.Google Scholar
60. F. G., Tinting maps, Athenceum 1389 (June 1854), 726.
61. T., Gallai, Kritische Graphen, I, Publ. Math. Inst. Hungar. Acad. Sci. 8 (1963), 165–192.
62. F., Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory (B) 63 (1995), 153–158.Google Scholar
63. M., Gardner, Martin Gardner Papers, Stanford University Department of Special Collections, SC 647, Box 52, Folder 6, 1980.Google Scholar
64. M., Gardner, Mathematical games, Scientific American 242 (February 1980), 14–21.Google Scholar
65. M. K., Goldberg, On multigraphs of almost maximal chromatic class (in Russian), Diskret. Analiz 23 (1973), 3–7.Google Scholar
66. M. K., Goldberg, Edge-coloring of multigraphs; recoloring technique, J. Graph Theory 8 (1984), 123–137.Google Scholar
67. G., Gonthier, Formal proof – the four-color theorem, Notices Amer. Math. Soc. 55(11) (2008), 1382–1393.Google Scholar
68. P. R., Goodey, Hamiltonian circuits in polytopes with even sides, Israel J. Math. 22 (1975), 52–56.Google Scholar
69. H., Grötzsch, Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz fur dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe 8 (1959), 109–120.Google Scholar
70. R. P., Gupta, On the chromatic index and the cover index of a multigraph, Theory and Applications of Graphs (Michigan, 1976) (eds. A., Donald and B., Eckmann), Lecture Notes in Math. 642, Springer (1978), 91–110.Google Scholar
71. A., Gyárfás, On Ramsey covering-numbers, Infinite and Finite Sets, (Keszthely 1973) (eds. A., Hajnal, R., Rado and V. T., Sos), Coll. Math. Soc. János Bolyai 10, North-Holland (1975), 801–816.Google Scholar
72. A., Gyárfás, Problems from the world surrounding perfect graphs, Zastos. Mat. XIX (1987), 413–441.Google Scholar
73. A., Gyárfás and P., Erdős, Split and balanced colorings of complete graphs, Discrete Math. 200 (1999), 79–86.Google Scholar
74. H., Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich 88 (1943), 133–143.Google Scholar
75. A., Hajnal and E., Szemerédi, Proof of a conjecture of Erdős, Infinite and Finite Sets (eds. P., Erdos, A., Renyi and V. T., Sos), Coll. Math. Soc. János Bolyai 10, North Holland (1970), 601–623.Google Scholar
76. R., Hao, J., Niu, X., Wang, C. Q., Zhang and T., Zhang, A note on Berge–Fulkerson coloring, Discrete Math. 309 (2009), 4235–4240.Google Scholar
77. P., Hell, Z., Pan, T.-L., Wong and X., Zhu, Adaptable chromatic number of graph products, Discrete Math. 309 (2009), 6153–6159.Google Scholar
78. P., Hell and X., Zhu, On the adaptable chromatic number of graphs, Europ. J. Combin. 29 (2008), 912–921.Google Scholar
79. D. S., Hochbaum, T., Nishizeki and D. B., Shmoys, A better than ‘best possible’ algorithm to edge color multigraphs, J. Algorithms 7 (1986), 79–104.Google Scholar
80. W., Hochstättler, A Hadwiger Conjecture for Hyperplane Arrangements, Technical report feu-dmo018.09, FernUniversität Hagen, 2009.
81. D. A., Holton, B., Manvel and B. D., McKay, Hamiltonian cycles in cubic 3-connected bipartite planar graphs, J. Combin. Theory (B) 38 (1985), 279–297.Google Scholar
82. B., Jackson and G., Ringel, Variations on Ringel's earth-moon problem, Discrete Math. 211 (2000), 233–242.Google Scholar
83. F., Jaeger, Nowhere-zero flow problems, Selected Topics in Graph Theory 3 (eds. L. W., Beineke and R. J., Wilson), Academic Press (1988), 71–95.Google Scholar
84. T. R., Jensen, Dense critical and vertex-critical graphs, Discrete Math. 258 (2002), 63–84.Google Scholar
85. T. R., Jensen and B., Toft, Graph Coloring Problems, Wiley, 1995.Google Scholar
86. J., Kahn, Asymptotically good list-colorings, J. Combin. Theory (A) 73 (1996), 1–59.Google Scholar
87. T., Kaiser, D., Král' and S., Norine, Unions of perfect matchings in cubic graphs, Topics in Discrete Mathematics (eds. M., Klazar et al.), Springer (2006), 225–230.Google Scholar
88. T., Kaiser and R., Šrkrekovski, Cycles intersecting edge-cuts of prescribed sizes, SIAM J. Discrete Math. 22 (2008), 861–874.Google Scholar
89. H., Kaul, A. V., Kostochka and G., Yu, On a graph packing conjecture by Bollobás, Eldridge and Catlin, Combinatorica 28 (2008), 469–485.Google Scholar
90. K., Kawarabayashi, Minors in 7-chromatic graphs, preprint.
91. K., Kawarabayashi, A. S., Pedersen and B., Toft, Double-critical graphs and complete minors, Electron. J. Combin. 17 (2010), R87.Google Scholar
92. K., Kawarabayashi, M. D., Plummer and B., Toft, Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture, J. Combin. Theory (B) 95 (2005), 152–167.Google Scholar
93. K., Kawarabayashi and B. A., Reed, Hadwiger's conjectureis decidable, Proc. 41stAnnual ACM Symposium on Theory of Computing, STOC '09 (2009), 445–454.Google Scholar
94. K., Kawarabayashi and Z.-X., Song, Independence number and clique minors, J. Graph Theory 56 (2007), 219–226.Google Scholar
95. K., Kawarabayashi and C., Thomassen, From the plane to higher surfaces, J. Combin. Theory (B) 102 (2012), 852–868.Google Scholar
96. K., Kawarabayashi and B., Toft, Any 7-chromatic graph has K7 or K4,4 as a minor, Combinatorica 25 (2005), 327–353.Google Scholar
97. A. K., Kelmans, Constructions of cubic bipartite 3-connected graphs without Hamiltonian cycles, Amer. Math. Soc. Transl. 158 (1994), 127–140.Google Scholar
98. H. A., Kierstead and A. V., Kostochka, A short proof of the Hajnal-Szemeredi theorem on equitable colouring, Combin. Probab. Comput. 17 (2008), 265–270.Google Scholar
99. H. A., Kierstead and S. G., Penrice, Recent results on a conjecture of Gyárfás, Proc. 21st S.-E. Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, 1990) (eds. F., Hoffmanet al.), Congr. Numer. 79 (1990), 182–186.Google Scholar
100. H. A., Kierstead and S. G., Penrice, Radius two trees specify χ-bounded classes, J. Graph Theory 18 (1994), 119–129.Google Scholar
101. H. A., Kierstead and W. T., Trotter, Planar graph coloring with an uncooperative partner, Planar Graphs (ed. W. T., Trotter), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 9, American Mathematical Society (1993), 85–93.Google Scholar
102. A. D., King, Claw-free Graphs and Two Conjectures on ω, Δ, and χ, Ph.D. thesis, Gill University, 2009.Google Scholar
103. H., Klein and M., Margraf, A remark on the conjecture of Erdős, Faber and Lovasz, J. Geom. 88 (2008), 116–119.Google Scholar
104. W., Klostermeyer and C. Q., Zhang, (2 + ε)-coloring of planar graphs with large odd-girth, J. Graph Theory 33 (2000), 109–119.Google Scholar
105. W., Knight, Computer generates verifiable mathematics proof, New Scientist Breaking News, 19 April 2005.Google Scholar
106. M., Kochol, Cubic graphs without a Petersen minor have nowhere-zero 5-flows, Acta Math. Univ. Comenian. (N.S.) 68 (1999), 249–252.Google Scholar
107. M., Kochol, An equivalent version of the 3-flow conjecture, J. Combin. Theory (B) 83 (2001), 258–261.Google Scholar
108. M., Kochol, Reduction of the 5-flow conjecture to cyclically 6-edge-connected snarks, J. Combin. Theory (B) 90 (2004), 139–145.Google Scholar
109. M., Kochol, Restrictions on smallest counterexamples to the 5-flow conjecture, Combinatorica 26 (2006), 83–89.Google Scholar
110. D., König, Theorie der Endlichen und Unendlichen Graphen, Akademische Verlagsge-sellschaft M. B. H., Leipzig, 1936; reprinted by Chelsea, 1950, and B. G., Teubner, 1986; English transl., Birkhäuser, 1990.
111. A. V., Kostochka and M. P., Yancey, Ore's conjecture on color-critical graphs is almost true, arXiv:1209.1050, 2012.Google Scholar
112. A. V., Kostochka and X., Zhu, Adapted list coloring of graphs and hypergraphs, SIAM J. Discrete Math. 22 (2008), 398–408.Google Scholar
113. F., Kramer and H., Kramer, A survey on the distance-colouring of graphs, Discrete Math. 308 (2008), 422–426.Google Scholar
114. H.-J., Lai, X., Li and H., Poon, Nowhere zero 4-flow in regular matroids, J. Graph Theory 49 (2005), 196–204.Google Scholar
115. L., Lovász, Tutte's flow conjectures, tlovering.files.wordpress.com/2012/06/laszloes-say.pdf, 2012.Google Scholar
116. L., Lovász, C., Thomassen, Y., Wu and C. Q., Zhang, Nowhere-zero 3-flows and modulo k-orientations, J. Combin. Theory (B) 103 (2013), 587–598.Google Scholar
117. A., Mansfield, Determining the thickness of graphs is NP-hard, Math. Proc. Cambridge Philos. Soc. 93 (1983), 9–23.Google Scholar
118. M., Matamala and J., Zamora, Nowhere-zero 5-flows and even (1,2)-factors, Graphs Combin. 29 (2013), 609–616.Google Scholar
119. G., Mazzuoccolo, The equivalence of two conjectures of Berge and Fulkerson, J. Graph Theory 68 (2011), 125–128.Google Scholar
120. B. D., McKay, A note on the history of the four-colour conjecture, J. Graph Theory 72 (2013), 361–363.Google Scholar
121. M., Mirzakhani, A small non-4-choosable planar graph, Bull. Inst. Combin. Appl. 17 (1996), 15–18.Google Scholar
122. M., Molloy and B. A., Reed, A bound on the total chromatic number, Combinatorica 18 (1998), 241–280.Google Scholar
123. M., Molloy and B. A., Reed, Graph Colouring and the Probabilistic Method, Algorithms and Combinatorics 23, Springer-Verlag, 2002.Google Scholar
124. M., Molloy and G., Thron, The adaptable choosability number grows with the choosability number, Discrete Math. 311 (2011), 2268–2271.Google Scholar
125. M., Molloy and G., Thron, An asymptotically tight bound on the adaptable chromatic number, J. Graph Theory 71 (2012), 331–351.Google Scholar
126. M., Montassier, A., Raspaud and X., Zhu, An upper bound on adaptive choosability of graphs, Europ. J. Combin. 30 (2009), 351–355.Google Scholar
127. J., Nešetřil and P., Ossona de Mendez, Grad and classes with bounded expansion III. Restricted graph homomorphism dualities, Europ. J. Combin. 29 (2008), 1012–1024.Google Scholar
128. J. G., Oxley, Matroid Theory (2nd edn.), Oxford University Press, 2006.
129. V., Patel, Unions of perfect matchings in cubic graphs and implications of the Berge-Fulkerson conjecture, CDAM Research Report LSE-CDAM-2006-06, 2006.
130. A. S., Pedersen and B., Toft, A basic elementary extension of the Duchet-Meyniel theorem, Discrete Math. 310 (2010), 480–488.Google Scholar
131. J., Petersen, Die Theorie der regulären Graphs, Acta Math. 15 (1891), 193–220.Google Scholar
132. M. D., Plummer, M., Stiebitz and B., Toft, On a special case of Hadwiger's conjecture, Discuss. Math. Graph Theory 23 (2003), 333–363.Google Scholar
133. B. A., Reed, ω,Δ, and χ, J. Graph Theory 27 (1998), 177–212.
134. B. A., Reed, A strengthening of Brooks' theorem, J. Combin. Theory (B) 76 (1999), 136–149.Google Scholar
135. G., Ringel, Fäirbungsprobleme auf Flächen und Graphen, Math. Monographien 2, VEB Deutscher Verlag der Wissenschaften, 1959.Google Scholar
136. R., Rizzi, Approximating the maximum 3-edge-colorable subgraph problem, Discrete Math. 309 (2009), 4166–4170.Google Scholar
137. N., Robertson, D. P., Sanders, P. D., Seymour and R., Thomas, The four-colour theorem, J. Combin. Theory (B) 70 (1997), 2–44.Google Scholar
138. N., Robertson, P. D., Seymour and R., Thomas, Hadwiger's conjecture for K6-free graphs, Combinatorica 13 (1993), 279–361.Google Scholar
139. N., Robertson, P. D., Seymour and R., Thomas, Tutte's edge-colouring conjecture, J. Combin. Theory (B) 70 (1997), 166–183.Google Scholar
140. V., Rödl, A., Ruciński and A., Taraz, Hypergraph packing and graph embedding, Combin. Probab. Comput. 8 (1999), 363–376.Google Scholar
141. D., Romero and A., Sánchez-Arroyo, Advances on the Erdős-Faber-Lovász conjecture, Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh (eds. G., Grimmett and C., McDiarmid), Oxford Univ. Press (2007), 285–298.Google Scholar
142. M. R., Salavatipour, The three color problem for planar graphs, Technical report CSRG-458, Department of Computer Science, University of Toronto, July 2002.
143. D. P., Sanders and Y., Zhao, A note on the three color problem, Graphs Combin. 11 (1995), 91–94.Google Scholar
144. N. W., Sauer, Vertex partition problems, Combinatorics, Paul Erdős is Eighty, 1 (eds. D., Miklós, V.T., Sós and T., Szőnyi), Bolyai Society Mathematical Studies, János Bolyai Mathematical Society (1993), 361–377.Google Scholar
145. N. W., Sauer and J. H., Spencer, Edge-disjoint placements of graphs, J. Combin. Theory (B) 15 (1978), 295–302.Google Scholar
146. A., Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics 24, Springer, 2003.
147. P. D., Seymour, Some unsolved problems on 1-factorizations of graphs, Graph Theory and Related Topics (Waterloo, Ontario, 1977) (eds. J. A., Bondy and U. S. R., Murty), Academic Press (1979), 367–368.Google Scholar
148. P. D., Seymour, On multi-colorings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. 38 (1979), 423–460.Google Scholar
149. M., Simonovits, On colour-critical graphs, Studia Sci. Math. Hungar. 7 (1972), 67–81.Google Scholar
150. A., Soifer, The Mathematical Coloring Book, Springer, 2009.Google Scholar
151. E., Steffen, Tutte's 5-flow conjecture for graphs of nonorientable genus 5, J. Graph Theory 22 (1996), 309–319.Google Scholar
152. M., Stehlik, Minimal connected τ-critical hypergraphs, Graphs Combin. 22 (2006), 421–426.Google Scholar
153. R., Steinberg, The state of the three color problem, Quo Vadis, Graph Theory? (eds. J., Gimbel, J. W., Kennedy and L. V., Quintas), Annals of Discrete Math. 55, North-Holland (1993), 211–248.Google Scholar
154. J. P., Steinberger, An unavoidable set of D-reducible configurations, Trans. Amer. Math. Soc. 362 (2010), 6633–6661.Google Scholar
155. M., Stiebitz, A relaxed version of the Erdős-Lovász Tihany conjecture, manuscript, TU Ilmenau, 2011.
156. M., Stiebitz, D., Scheide, B., Toft and L. M., Favrholdt, Graph Edge Coloring, Wiley, 2012.Google Scholar
157. W. R., Stromquist, Some Aspects of the Four Color Problem, Ph.D. thesis, Harvard University, 1975.Google Scholar
158. D. P., Sumner, Subtrees of a graph and chromatic number, Theory and Applications of Graphs, Proc. 4th. International Graph Theory Conference (Kalamazoo, 1980) (eds. G., Chartrand et al.), Wiley (1981), 557–576.Google Scholar
159. C., Thomassen, Every planar graph is 5-choosable, J. Combin. Theory (B) 62 (1994), 180–181.Google Scholar
160. C., Thomassen, A short list color proof of Grötzsch's theorem, J. Combin. Theory (B) 88 (2003), 189–192.Google Scholar
161. C., Thomassen, The weak 3-flow conjecture and the weak circular flow conjecture, J. Combin. Theory (B) 102 (2012), 521–529.Google Scholar
162. B., Toft, On the maximal number of edges of critical k-chromatic graphs, Studia Sci. Math. 5 (1970), 461–470.Google Scholar
163. B., Toft, Two theorems on critical 4-chromatic graphs, Studia Sci. Math. 7 (1972), 83–89.Google Scholar
164. W. T., Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 80–91.Google Scholar
165. W. T., Tutte, On the algebraic theory of graph colourings, J. Combin. Theory 1 (1966), 15–50.Google Scholar
166. W. T., Tutte, Colouring problems, Math. Intelligencer 1 (1978), 72–75.Google Scholar
167. V. G., Vizing, Some unsolved problems in graph theory (in Russian), Uspekhi Mat. Nauk. 23 (1968), 117–134; English transl. in Russian Math. Surveys23 (1968), 125–141.Google Scholar
168. V. G., Vizing, Colouring the vertices of a graph in prescribed colours (in Russian), Diskret. Analiz 29 (1976), 3–10.Google Scholar
169. M., Voigt, List colourings of planar graphs, Discrete Math. 120 (1993), 215–219.Google Scholar
170. K., Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570–590.Google Scholar
171. G., Wegner, Graphs with Given Diameter and a Coloring Problem, Technical report, University of Dortmund, 1977.
172. R., Wilson, Four Colors Suffice: How the Map Problem was Solved (revised color edn.), Princeton Science Library, 2014.Google Scholar
173. C. Q., Zhang, Integer Flows and Cycle Covers of Graphs, Marcel Dekker, 1997.Google Scholar
174. C. Q., Zhang, Circular flows of nearly Eulerian graphs and vertex-splitting, J. Graph Theory 40 (2002), 147–161.Google Scholar
175. Y., Zhao, 3-coloring graphs embedded in surfaces, J. Graph Theory 32 (2000), 140–143.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
×