On a recolouring version of Hadwiger’s conjecture

EUROCOMB’23

Abstract
We prove that for any $\varepsilon>0$, for any large enough $t$, there is a graph $G$ that admits no $K_t$-minor but admits a $(\frac32-\varepsilon)t$-colouring that is ``frozen‘‘ with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981.

Pages:
142–148
References

Armen S. Asratian. A note on transformations of edge colorings of bipartite graphs. Journal of Combinatorial Theory, Series B, 99(5):814-818, 2009.
https://doi.org/10.1016/j.jctb.2009.01.001

Armen S. Asratian and Carl Johan Casselgren. Solution of Vizing's problem on interchanges for the case of graphs with maximum degree 4 and related results. Journal of Graph Theory, 82(4):350-373, 2016.
https://doi.org/10.1002/jgt.21906

Marthe Bonamy, Nicolas Bousquet, Carl Feghali, and Matthew Johnson. On a conjecture of Mohar concerning Kempe equivalence of regular graphs. Journal of Combinatorial Theory, Series B, 135:179-199, 2019.
https://doi.org/10.1016/j.jctb.2018.08.002

Thomas Böhme, Alexandr Kostochka, and Andrew Thomason. Hadwiger numbers and over-dominating colourings. Discrete Mathematics, 310(20):2662-2665, 2010. Graph Theory - Dedicated to Carsten Thomassen on his 60th Birthday.
https://doi.org/10.1016/j.disc.2010.03.024

Leif K. Jørgensen. Contractions to K8. Journal of Graph Theory, 18(5):431-448, 1994.
https://doi.org/10.1002/jgt.3190180502

Tom Kelly and Luke Postle. A local epsilon version of reed's conjecture. Journal of Combinatorial Theory, Series B, 141:181-222, 2020.
https://doi.org/10.1016/j.jctb.2019.08.001

Alfred B. Kempe. On the geographical problem of the four colours. American journal of mathematics, 2(3):193-200, 1879.
https://doi.org/10.2307/2369235

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

Alexandr 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

Matthias Kriesell. A note on uniquely 10-colorable graphs. Journal of Graph Theory, 98(1):24-26, 2021.
https://doi.org/10.1002/jgt.22679

Michel Las Vergnas and Henri Meyniel. Kempe classes and the Hadwiger conjecture. Journal of Combinatorial Theory, Series B, 31(1):95-104, 1981.
https://doi.org/10.1016/S0095-8956(81)80014-7

Henry Meyniel. Les 5-colorations d'un graphe planaire forment une classe de commutation unique. J. Comb. Theory, Ser. B, 24:251-257, 1978.
https://doi.org/10.1016/0095-8956(78)90042-4

Bojan Mohar. Kempe equivalence of colorings. In Graph Theory in Paris, pages 287-297. Springer, 2006.
https://doi.org/10.1007/978-3-7643-7400-6_22

Bojan Mohar and Jesús Salas. A new Kempe invariant and the (non)-ergodicity of the Wang-Swendsen-Koteckỳ algorithm. Journal of Physics A: Mathematical and Theoretical, 42(22):225204, 2009.
https://doi.org/10.1088/1751-8113/42/22/225204

Alan D. Sokal. A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models. arXiv preprint cond-mat/0004231, 2000.

Zi-Xia Song and Robin Thomas. The extremal function for k9 minors. Journal of Combinatorial Theory, Series B, 96(2):240-252, 2006.
https://doi.org/10.1016/j.jctb.2005.07.008

Andrew Thomason. An extremal function for contractions of graphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 95, pages 261-265.Cambridge University Press, 1984.
https://doi.org/10.1017/S0305004100061521

Andrew Thomason. The extremal function for complete minors. Journal of Combinatorial Theory, Series B, 81(2):318-338, 2001.
https://doi.org/10.1006/jctb.2000.2013

Jan van den Heuvel. The complexity of change. Surveys in combinatorics, 409(2013):127-160, 2013.
https://doi.org/10.1017/CBO9781139506748.005

Eric Vigoda. Improved bounds for sampling colorings. Journal of Mathematical Physics, 41(3):1555-1569, 2000.
https://doi.org/10.1063/1.533196

Vadim G. Vizing. On an estimate of the chromatic class of a p-graph. Discret Analiz, 3:25-30, 1964.

Vadim G. Vizing. Some unsolved problems in graph theory. Russian Mathematical Surveys, 23(6):125, 1968.
https://doi.org/10.1070/RM1968v023n06ABEH001252

David R Wood. A note on hadwiger's conjecture. arXiv preprint arXiv:1304.6510, 2013.

Metrics

0

Views

0

PDF views