Refined list version of Hadwiger’s Conjecture

Yangyan Gu; Yiting Jiang; David Wood; Xuding Zhu

doi:10.5817/CZ.MUNI.EUROCOMB23-071

Refined list version of Hadwiger’s Conjecture

EUROCOMB’23

Yangyan Gu Yiting Jiang David Wood Xuding Zhu

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-071

PDF

Abstract

Assume $\lambda=\{k_1,k_2, \ldots, k_q\}$ is a partition of $k_{\lambda} = \sum_{i=1}^q k_i$. A $\lambda$-list assignment of $G$ is a $k_\lambda$-list assignment $L$ of $G$ such that the colour set $\bigcup_{v \in V(G)}L(v)$ can be partitioned into $|\lambda|= q$ sets $C_1,C_2,\ldots,C_q$ such that for each $i$ and each vertex $v$ of $G$, $|L(v) \cap C_i| \ge k_i$. We say $G$ is $\lambda$-choosable if $G$ is $L$-colourable for any $\lambda$-list assignment $L$ of $G$. The concept of $\lambda$-choosability is a refinement of choosability that puts $k$-choosability and $k$-colourability in the same framework. If $|\lambda|$ is close to $k_\lambda$, then $\lambda$-choosability is close to $k_\lambda$-colourability; if $|\lambda|$ is close to $1$, then $\lambda$-choosability is close to $k_\lambda$-choosability. This paper studies Hadwiger‘s Conjecture in the context of $\lambda$-choosability. Hadwiger‘s Conjecture is equivalent to saying that every $K_t$-minor-free graph is $\{1 \star (t-1)\}$-choosable for any positive integer $t$. We prove that for $t \ge 5$, for any partition $\lambda$ of $t-1$ other than $\{1 \star (t-1)\}$, there is a $K_t$-minor-free graph $G$ that is not $\lambda$-choosable. We then construct several types of $K_t$-minor-free graphs that are not $\lambda$-choosable, where $k_\lambda - (t-1)$ gets larger as $k_\lambda-|\lambda|$ gets larger.

Pages:
511–517

References

N. Alon, Zs. Tuza, M. Voigt. Choosability and fractional chromatic numbers, Discrete Math. 165/166, 31-38, 1997.
https://doi.org/10.1016/S0012-365X(96)00159-8

K. Appel, W. Haken. Every planar map is four colourable. I. Discharging. Illinois J. Math., 21(3):429-490, 1977.
https://doi.org/10.1215/ijm/1256049011

K. Appel, W. Haken, J. Koch. Every planar map is four colourable. II. Reducibility. Illinois J. Math., 21(3):491-567, 1977.
https://doi.org/10.1215/ijm/1256049012

J. Barát, G. Joret and D.R. Wood. Disproof of the list Hadwiger conjecture. Electronic J. Combin., 18(1), P232, 2011.
https://doi.org/10.37236/719

M. Delcourt, L. Postle. Reducing linear Hadwiger's conjecture to coloring small graphs. arXiv:2108.01633.

G. A. Dirac. A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc., 27:85-92, 1952.
https://doi.org/10.1112/jlms/s1-27.1.85

P. Erdős, A.L.Rubin, H.Taylor, Choosability in graphs, in: Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium XXVI, 1979, pp. 125-157.

H. Hadwiger. Uber eine Klassifikation der Streckenkomplexe. Vierteljschr. Naturforsch. Ges. Zürich, 88:133-142, 1943.

K. Kawarabayashi. On the connectivity of minimum and minimal counterexamples to Hadwiger's Conjecture. J. Combin. Theory Ser. B, 97(1):144-150, 2007.
https://doi.org/10.1016/j.jctb.2006.04.004

K. Kawarabayashi, B. Mohar. Some recent progress and applications in graph minor theory. Graphs Combin., 23(1):1-46, 2007.
https://doi.org/10.1007/s00373-006-0684-x

A. Kemnitz, M. Voigt. A note on non-4-list colourable planar graphs, Electron. J. Combin. 25(2), #P2.46, 2018.
https://doi.org/10.37236/7320

A. V. Kostochka. The minimum Hadwiger number for graphs with a given mean degree of vertices. Metody Diskret. Analiz., (38):37-58, 1982.

A. V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica, 4(4):307-316, 1984.
https://doi.org/10.1007/BF02579141

S. Norin, L. Postle. Connectivity and choosability of graphs with no minor. J. Combin. Theory, Ser. B 158(1):283-300, 2021.
https://doi.org/10.1016/j.jctb.2021.02.001

S. Norin, L. Postle, and Z. Song. Breaking the degeneracy barrier for colouring graphs with no minor. arXiv:1910.09378v2, 2019.

L. Postle. Further progress towards Hadwiger's conjecture. arXiv:2006.11798, 2020.

L. Postle. An even better density increment theorem and its application to Hadwiger's conjecture. arXiv:2006.14945, 2020.

L. Postle. Further progress towards the list and odd versions of Hadwiger's conjecture. arXiv:2010.05999, 2020.

B. Reed, P. Seymour. Fractional colouring and Hadwiger's conjecture. J. Combin. Theory Ser. B, 74(2):147-152, 1998.
https://doi.org/10.1006/jctb.1998.1835

N. Robertson, D.P. Sanders, P. Seymour, R. Thomas. The four-colour theorem. J. Combin. Theory Ser. B, 70(1):2-44, 1997.
https://doi.org/10.1006/jctb.1997.1750

N. Robertson, P. Seymour, R. Thomas. Hadwiger's conjecture for free graphs}. Combinatorica, 13(3):279-361, 1993.
https://doi.org/10.1007/BF01202354

R. Steiner. Improved lower bound for the list chromatic number of graphs with no minor. Combin. Probab. Comput. 32(2): 326-333, 2023.
https://doi.org/10.1017/S0963548322000268

P. Seymour, Hadwiger's conjecture. In: Open Problems in Mathematics, Eds. J. F. Nash Jr. and M. Th. Rassias, 417-437, Springer, 2016.
https://doi.org/10.1007/978-3-319-32162-2_13

A. Thomason. An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc., 95(2):261-265, 1984.
https://doi.org/10.1017/S0305004100061521

V.G.Vizing, Coloring the vertices of a graph in prescribed colours, Diskret. Analiz 29 Metody Diskret. Anal. v Teorii Kodov i Shem (1976) 3-10, p. 101, (in Russian).

M. Voigt. List colourings of planar graphs. Discrete Math., 120 (1-3), 215-219, 1993.
https://doi.org/10.1016/0012-365X(93)90579-I

K. Wagner. Uber eine Eigenschaft der ebenen Komplexe. Mathematische Annalen, 114:570-590, 1937.
https://doi.org/10.1007/BF01594196

X. Zhu, A refinement of choosability of graphs. J. Combin. Theory, Ser. B 141 (2020) 143-164.
https://doi.org/10.1016/j.jctb.2019.07.006

Metrics