Refined list version of Hadwiger’s Conjecture
EUROCOMB’23
511–517
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
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Yangyan Gu, Yiting Jiang, David Wood, Xuding Zhu