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-dh8gc Total loading time: 0 Render date: 2024-11-05T02:38:34.458Z Has data issue: false hasContentIssue false

4 - Hadwiger's conjecture

Published online by Cambridge University Press:  05 May 2015

By
Ken-Ichi Kawarabayashi
Edited by
Lowell W. Beineke  and
Robin J. Wilson
Ken-Ichi Kawarabayashi
Affiliation:
National Institute of Informatics in Japan
Lowell W. Beineke
Affiliation:
Purdue University, Indiana
Robin J. Wilson
Affiliation:
The Open University, Milton Keynes
Get access

Summary

Hadwiger's conjecture states that any graph that does not have the complete graph Kk as a minor is (k − 1)-colourable. It is well known that the case k = 5 is equivalent to the four-colour theorem. In 1993 Robertson, Seymour and Thomas proved that the case k = 6 is also equivalent to the four-colour theorem. For k ≥ 7, the conjecture is still open. Our main focus in this chapter is to present recent results related to minimal counter-examples to Hadwiger's conjecture and some variations. We also consider algorithmic aspects of the conjecture and some of its variants, including the list-colouring version (which is false), the odd case of the conjecture, Hajós's conjecture and totally odd subdivisions, and Hadwiger's conjecture for some special classes of graphs.

Introduction

This chapter is motivated by Hadwiger's conjecture from 1943, which suggests a farreaching generalization of the four-colour theorem. It is among the most challenging open problems in all of graph theory.

Hadwiger's conjecture (strong version) For all k, every k-colourable graph contains the complete graph Kk as a minor.

For k ≤ 3, Hadwiger's conjecture is easy to prove, and for k = 4, it was proved independently by Hadwiger himself [31] and Dirac [21]. For k = 5, however, it becomes extremely difficult. In 1937 Wagner [74] proved that this case is equivalent to the four-colour theorem, so, given that result in [2], [3], [56], it follows that the case k = 5 also holds. In the deepest theorem in this area so far, Robertson, Seymour and Thomas [62] proved in 1993 that a minimal counter-example to the case k = 6 must have a vertex whose removal leaves a planar graph, so this case too follows from the four-colour theorem. For k ≥ 7, the conjecture is still open. For k = 7, Kawarabayashi and Toft [46] proved that every 7-chromatic graph has K7 or K4,4 as a minor, and recently Kawarabayashi [38] proved that every 7-chromatic graph has K7 or K3,5 as a minor.

Type
Chapter
Information
Topics in Chromatic Graph Theory , pp. 73 - 93
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. F. N., Abu-Khzam and M. A., Langston, Graph coloring and the immersion order, to appear.
2. K., Appel and W., Haken, Every planar map is four colorable, Part I. Discharging, Illinois J. Math. 21 (1977), 429–190.Google Scholar
3. 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
4. S., Arnborg and A., Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Appl. Math. 23 (1989), 11–24.Google Scholar
5. J., Balogh and A., Kostochka, Large minors in graphs with given independent number, Discrete Math. 311 (2011), 2204–2215.Google Scholar
6. J., Balogh, J., Lenz and H., Wu, Complete minors, independent sets, and chordal graphs, Discuss. Math. Graph Theory, to appear.
7. J., Barat, G., Joret and D., Wood, Disproof of the list Hadwiger conjecture, Electron. J. Combin. 18 (2011), P232.Google Scholar
8. H. L., Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput. 25 (1996), 1305–1317.Google Scholar
9. T., Böhme, K., Kawarabayashi, J., Maharry and B., Mohar, Linear connectivity forces large complete bipartite minors, J. Combin. Theory (B) 99 (2009), 557–582.Google Scholar
10. B., Bollobás and P. A., Catlin, Topological cliques of random graphs, J. Combin. Theory (B) 30 (1981), 224–227.Google Scholar
11. B., Bollobás and A., Thomason, Highly linked graphs, Combinatorica 16 (1996), 313–320.Google Scholar
12. H. D., Booth, R., Govindan, M. A., Langston and S., Ramachandramurthis, Sequential and parallel algorithms for K4-immersion testing, J. Algorithms 30 (1999), 344–378.Google Scholar
13. P. A., Catlin, A bound on the chromatic number of a graph, Discrete Math. 22 (1978), 81–83.Google Scholar
14. G., Chartrand, D., Geller and S., Hedetniemi, Graphs with forbidden subgraphs, J. Combin. Theory (B) 10 (1971), 12–41.Google Scholar
15. M., Chudnovsky and A. O., Fradkin, Hadwiger's conjecture for quasi-line graphs, J. Graph Theory 59 (2008), 17–33.Google Scholar
16. M., Chudnovsky and P., Seymour, Packing seagulls, Combinatorica, to appear.
17. V., Chvátal, On certain polytopes associated with graphs, J. Combin. Theory (B) 18 (1975), 138–154.Google Scholar
18. M., DeVos, Z., Dvořák, J., Fox, J., McDonald, B., Mohar and D., Scheide, A minimum degree condition forcing complete graph immersion, Combinatorica 34 (2014), 279–298.Google Scholar
19. M., DeVos, K., Kawarabayashi, B., Mohar and H., Okamura, Immersing small complete graphs, Ars Math. Contemp. 3 (2010), 139–146.Google Scholar
20. R., Diestel, Graph Theory (2nd edn.), Springer, 2000.Google Scholar
21. 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
22. G. A., Dirac, Trennende Knotenpunktmengen und Reduzibilität abstrakter Graphen mit Anwendung auf das Vierfarbenproblem, J. Reine Angew. Math. 204 (1960), 116–131.Google Scholar
23. G. A., Dirac, Homomorphism theorems for graphs, J. Reine Angew. Math. 153 (1964), 69–80.Google Scholar
24. G. A., Dirac, On the structure of 5- and 6-chromatic abstract graphs, Math. Ann. 214/215 (1964), 43–52.Google Scholar
25. P., Duchet and H., Meyniel, On Hadwiger's number and the stability number, Graph Theory (Cambridge, 1981), North-Holland (1982), 71–73.Google Scholar
26. P., Erdős and S., Fajtlowicz, On the conjecture of Hajós, Combinatorica 1 (1981), 141–143.Google Scholar
27. J., Fox, Complete minors and independence number, SIAM J. Discrete Math. 24 (2010) 1313–1321.Google Scholar
28. A. O., Fradkin, Clique minors in claw-free graphs, J. Combin. Theory (B) 102 (2012), 71–85.Google Scholar
29. J., Geelen, B., Gerards, B., Reed, P., Seymour and A., Vetta, On the odd variant of Hadwiger's conjecture, J. Combin. Theory (B) 99 (2009), 20–29.Google Scholar
30. B., Gerards, An extension of Konig's theorem to graphs with no odd-K4, J. Combin. Theory (B) 47 (1989), 330–348.Google Scholar
31. H., Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zurich 88 (1943), 133–142.Google Scholar
32. M. R., Henzinger, S., Rao and H. N., Gabow, Computing vertex connectivity: new bounds from old techniques, J. Algorithms 34 (2000), 222–250.Google Scholar
33. T. R., Jensen and B., Toft, Graph Coloring Problems, Wiley–Interscience, 1995.Google Scholar
34. L., Jørgensen, Contraction to K8, J. Graph Theory 18 (1994), 431–448.Google Scholar
35. K., Kawarabayashi, Rooted minors problem in highly connected graphs, Discrete Math. 287 (2004), 121–123.Google Scholar
36. K., Kawarabayashi, On the connectivity of minimal counterexamples to Hadwiger's conjecture, J. Combin. Theory (B) 97 (2007), 144–150.Google Scholar
37. K., Kawarabayashi, Note on coloring graphs with no odd-Kk-minors, J. Combin. Theory (B) 99 (2009), 738–741.Google Scholar
38. K., Kawarabayashi, Minors in 7-chromatic graphs, preprint.
39. K., Kawarabayashi, A., Kostochka and G., Yu, On sufficient degree conditions for a graph to be k-linked, Combin. Probab. Comput. 15 (2006), 685–694.Google Scholar
40. K., Kawarabayashi and B., Mohar, A relaxed Hadwiger's conjecture for list-colorings, J. Combin. Theory (B) 97 (2007), 647–651.Google Scholar
41. K., Kawarabayashi, S., Norine, R., Thomas and P., Wollan, K6 minors in large 6-connected graphs, submitted.
42. K., Kawarabayashi, M., Plummer and B., Toft, Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture, J. Combin. Theory (B) 96 (2005), 152–167.Google Scholar
43. K., Kawarabayashi and B., Reed, Fractional coloring and the odd Hadwiger's conjecture, Europ. J. Combin. 29 (2008), 411–417.Google Scholar
44. K., Kawarabayashi and B., Reed, Hadwiger's conjecture is decidable, STOC'09 Proc. 2009 ACM International Symposium on Theory ofComputing, ACM (2009), 445–454.Google Scholar
45. K., Kawarabayashi and Z., Song, Some remarks on the odd Hadwiger's conjecture, Combinatorica 27 (2007), 429–438.Google Scholar
46. K., Kawarabayashi and B., Toft, Any 7-chromatic graph has K7 or K4, 4 as a minor, Combinatorica 25 (2005), 327–353.Google Scholar
47. K., Kawarabayashi and G., Yu, Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's conjecture, J. Combin. Theory (B) 103 (2013), 320–326.Google Scholar
48. J., Komlós and E., Szeméredi, Topological cliques in graphs II, Combin. Prob. Comput. 5 (1996), 79–80.Google Scholar
49. A., Kostochka, The minimum Hadwiger number for graphs with a given mean degree of vertices, Metody Diskret. Analiz 38 (1982), 37–58.Google Scholar
50. A., Kostochka, Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica 4 (1984), 307–316.Google Scholar
51. F., Lescure and H., Meyniel, On a problem upon configurations contained in graphs with given chromatic number, Graph Theory in Memory ofG. A. Dirac (Sandbjerg, 1985), Ann. Discrete Math. 41, North-Holland (1989), 325–331.Google Scholar
52. W., Mader, Homomorphiesatze fur Graphen, Math. Ann. 178 (1968), 154–168.Google Scholar
53. W., Mader, Existenz n-fach zusammenhängender Teilgraphen in Graphen genilgend grosser Kantendichte, Abh. Math. Sem. Univ. Hamburg 37 (1972), 86–97.Google Scholar
54. M., Plummer, M., Stiebitz and B., Toft, On a special case of Hadwiger's conjecture, Discuss. Math. Graph Theory 23 (2003), 333–363.Google Scholar
55. B., Reed and P. D., Seymour, Fractional chromatic number and Hadwiger's conjecture, J. Combin. Theory (B) 74 (1998), 147–152.Google Scholar
56. N., Robertson, D. P., Sanders, P. D., Seymour and R., Thomas, The four-color theorem, J. Combin. Theory (B) 70 (1997), 2–44.Google Scholar
57. N., Robertson and P. D., Seymour, Graph minors XIII. The disjoint paths problem, J. Combin. Theory (B) 63 (1995), 65–110.Google Scholar
58. N., Robertson and P. D., Seymour, Graph minors XVII. Taming a vortex, J. Combin. Theory (B) 77 (1999), 162–210.Google Scholar
59. N., Robertson and P. D., Seymour, Graph minors XVI. Excluding a non-planar graph, J. Combin. Theory (B) 89 (2003), 43–76.Google Scholar
60. N., Robertson and P. D., Seymour, Graph minors XX. Wagner's conjecture, J. Combin. Theory (B) 92 (2004), 325–357.Google Scholar
61. N., Robertson and P. D., Seymour, Graph minors XXIII, Nash-Williams' immersion conjecture, J. Combin. Theory (B) 100 (2010), 181–205.Google Scholar
62. N., Robertson, P. D., Seymour and R., Thomas, Hadwiger's conjecture for K6-free graphs, Combinatorica 13 (1993), 279–361.Google Scholar
63. A., Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003.Google Scholar
64. Z., Song and R., Thomas, The extremal function for K9 minors, J. Combin. Theory (B) 96 (2006), 240–252.Google Scholar
65. R., Thomas and P., Wollan, An improved linear edge bound for graph linkages, Europ. J. Combin. 26 (2005), 309–324.Google Scholar
66. A., Thomason, An extremal function for contractions of graphs, Math. Proc. Cambridge Philos. Soc. 95 (1984), 261–265.Google Scholar
67. A., Thomason, The extremal function for complete minors, J. Combin. Theory (B) 81 (2001), 318–338.Google Scholar
68. C., Thomassen, Graph decomposition with applications to subdivisions and path systems modulok, J. Graph Theory 7 (1983) 261–271.Google Scholar
69. C., Thomassen, Parity, cycle space, and K4-subdivision in graphs, Surveys in Combin-atorics, 1999, London Math. Soc. Lecture Notes 267, Cambridge University Press (1999), 223–238.Google Scholar
70. C., Thomassen, Totally odd K4-subdivisions in 4-chromatic graphs, Combinatorica 21 (2001), 417–443.Google Scholar
71. C., Thomassen, Some remarks on Hajós' conjecture, J. Combin. Theory (B) 93 (2005), 95–105.Google Scholar
72. B., Toft, Problem 11, Recent Advances in Graph Theory (ed. M., Fiedler), Academia Praha (1975), 543–544.
73. B., Toft, A survey of Hadwiger's conjecture, Congr. Numer. 115 (1996), 249–283.Google Scholar
74. K., Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570–590.Google Scholar
75. K., Wagner, Beweis einer Abschwachung der Hadwiger-Vermutung, Math. Ann. 153 (1964), 139–141.Google Scholar
76. D., Wood, Independent sets in graphs with an excluded clique minor, Discrete Math. Theor. Comput. Sci. 9 (2007), 171–175.Google Scholar
77. D. R., Woodall, Subcontraction-equivalence and Hadwiger's conjecture, J. Graph Theory 11 (1987), 197–204.Google Scholar
78. W., Zang, Proof of Toft's conjecture: every graph containing no fully odd K4 is 3-colorable, J. Combin. Optim. 2 (1998), 117–188.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
×