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

λ = {k_{1}, k_{2}, \dots, k_{q}}

is a partition of

k_{λ} = \sum_{i = 1}^{q} k_{i}

. A

λ

-list assignment of

G

is a

k_{λ}

-list assignment

L

of

G

such that the colour set

⋃_{v \in V (G)} L (v)

can be partitioned into

| λ | = q

sets

C_{1}, C_{2}, \dots, C_{q}

such that for each

i

and each vertex

v

of

G

,

| L (v) \cap C_{i} | \geq k_{i}

. We say

G

is

λ

-choosable if

G

is

L

-colourable for any

λ

-list assignment

L

of

G

. The concept of

λ

-choosability is a refinement of choosability that puts

k

-choosability and

k

-colourability in the same framework. If

| λ |

is close to

k_{λ}

, then

λ

-choosability is close to

k_{λ}

-colourability; if

| λ |

is close to

1

, then

λ

-choosability is close to

k_{λ}

-choosability. This paper studies Hadwiger‘s Conjecture in the context of

λ

-choosability. Hadwiger‘s Conjecture is equivalent to saying that every

K_{t}

-minor-free graph is

{1 ⋆ (t - 1)}

-choosable for any positive integer

t

. We prove that for

t \geq 5

, for any partition

λ

of

t - 1

other than

{1 ⋆ (t - 1)}

, there is a

K_{t}

-minor-free graph

G

that is not

λ

-choosable. We then construct several types of

K_{t}

-minor-free graphs that are not

λ

-choosable, where

k_{λ} - (t - 1)

gets larger as

k_{λ} - | λ |

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