On a recolouring version of Hadwiger’s conjecture
EUROCOMB’23
142–148
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.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Marthe Bonamy, Marc Heinrich, Clément Legrand-Duchesne, Jonathan Narboni