×

Strengthening Hadwiger’s conjecture for 4- and 5-chromatic graphs. (English) Zbl 07796408

Summary: H. Hadwiger’s famous coloring conjecture [Vierteljahresschr. Naturforsch. Ges. Zürich 88, 133–142 (1943; Zbl 0061.41308)] states that every \(t\)-chromatic graph contains a \(K_t\)-minor. F. Holroyd [Bull. Lond. Math. Soc. 29, No. 2, 139–144 (1997; Zbl 0876.05033)] conjectured the following strengthening of Hadwiger’s conjecture: If \(G\) is a \(t\)-chromatic graph and \(S \subseteq V(G)\) takes all colors in every \(t\)-coloring of \(G\), then \(G\) contains a \(K_t\)-minor rooted at \(S\).
We prove this conjecture in the first open case of \(t = 4\). Notably, our result also directly implies a stronger version of Hadwiger’s conjecture for 5-chromatic graphs as follows: Every 5-chromatic graph contains a \(K_5\)-minor with a singleton branch-set. In fact, in a 5-vertex-critical graph we may specify the singleton branch-set to be any vertex of the graph.

MSC:

05C15 Coloring of graphs and hypergraphs
05C83 Graph minors
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Appel, K.; Haken, W., Every planar map is four colorable, I. Discharging. Ill. J. Math., 3, 429-490 (1977) · Zbl 0387.05009
[2] Appel, K.; Haken, W.; Koch, J., Every planar map is four colorable, II. Reducibility. Ill. J. Math., 3, 491-567 (1977) · Zbl 0387.05010
[3] Delcourt, M.; Postle, L., Reducing linear Hadwiger’s conjecture to coloring small graphs (2021), arXiv preprint
[4] Demasi, L.; Mohar, B., Four terminal planar Delta-Wye reducibility via rooted \(K_{2 , 4}\)-minors, 1728-1742 · Zbl 1371.05053
[5] Diestel, R., Graph Theory. GTM (2016), Springer
[6] Dirac, G. A., A property of 4-chromatic graphs and some remarks on critical graphs. J. Lond. Math. Soc., 85-92 (1952) · Zbl 0046.41001
[7] Ellen Fich, F.; Kündgen, A.; Pelsmajer, M. J.; Ramamurthi, R., Graph minors and reliable single message transmission. SIAM J. Discrete Math., 4, 815-847 (2005) · Zbl 1102.68009
[8] Fabila-Monroy, R.; Wood, D. R., Rooted \(K_4\)-minors. Electron. J. Comb., 2 (2013) · Zbl 1295.05218
[9] Hadwiger, H., Über eine Klassifikation der Streckenkomplexe. Vierteljahrsschr. Nat.forsch. Ges. Zür., 133-143 (1943) · Zbl 0061.41308
[10] Hayashi, K.; Kawarabayashi, K.-i., Rooted topological minors on four vertices. J. Comb. Theory, Ser. B, Part 1, 146-185 (2023) · Zbl 1504.05272
[11] Holroyd, F., Strengthening Hadwiger’s conjecture. Bull. Lond. Math. Soc., 139-144 (1997) · Zbl 0876.05033
[12] Kriesell, M.; Mohr, S., Rooted complete minors in line graphs with a Kempe coloring. Graphs Comb., 551-557 (2019) · Zbl 1425.05060
[13] Kriesell, M.; Mohr, S., Kempe chains and rooted minors (2019), arXiv preprint
[14] Linusson, S.; Wood, D. R., Thomassen’s choosability argument revisited. SIAM J. Discrete Math., 4, 1632-1637 (2010) · Zbl 1221.05290
[15] Marx, D.; Seymour, P.; Wollan, P., Rooted grid minors. J. Comb. Theory, Ser. B, 428-437 (2017) · Zbl 1350.05158
[16] Norin, S.; Postle, L.; Song, Z.-X., Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor. Adv. Math. (2023) · Zbl 1512.05144
[17] Robertson, R.; Seymour, P.; Thomas, R., Hadwiger’s conjecture for \(K_6\)-free graphs. Combinatorica, 279-361 (1993) · Zbl 0830.05028
[18] Robertson, R.; Sanders, D.; Seymour, P.; Thomas, R., The four-colour theorem. J. Comb. Theory, Ser. B, 1, 2-44 (1997) · Zbl 0883.05056
[19] Seymour, P., Hadwiger’s conjecture, 417-437 · Zbl 1347.05079
[20] Wagner, K., Über eine Eigenschaft der ebenen Komplexe. Math. Ann., 570-590 (1937) · Zbl 0017.19005
[21] Wollan, P., Extremal functions for rooted minors. J. Graph Theory, 159-178 (2008) · Zbl 1151.05044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.