Complete minors in graphs with only a few colourings
Final Report Abstract
Hadwigers Vermutung von 1943 besagt, daß für jede natürliche Zahl k die Ecken eines beliebigen Graphen sich mit k Farben so färben lassen, daß benachbarte Ecken verschiedene Farben erhalten, oder aber dieser Graph k + 1 viele disjunkte, zusammenhängende, paarweise benachbarte Teilgraphen besitzt, einen sogenannten vollständigen Minor der Ordnung k + 1. Sie ist eine der wichtigsten offenen Fragen der Graphentheorie. In diesem Projekt wurde der Fall betrachtet, dass der vorgelegte Graph nur wenige Färbungen mit k Farben besitzt. Insbesondere wurde die Vermutung angegangen, dass jeder Graph mit einer Kempe-Färbung der Ordnung k und einer Transversale einen vollständigen Minoren der Ordnung k besitzt, sodass die Transversale auch die Taschen des Minors traversiert. Hierfür wurden Ergebnisse unter zusätzlichen Voraussetzungen gefunden, eine Verallgemeinerung hinsichtlich der Färbung als falsch erwiesen und weitere Ergebnisse über die Zusammenhangsstruktur entwickelt. Weitere Erkenntnisse über eindeutige Färbungen und Strukturen in Graphen konnten erzielt und veröffentlicht werden.
Publications
- Rooted complete minors in line graphs with a Kempe coloring, Graphs and Combinatorics 35.2 (2019), 551–557
Matthias Kriesell, Samuel Mohr
(See online at https://doi.org/10.1007/s00373-019-02012-7) - Long cycles and spanning subgraphs of locally maximal 1-planar graphs, Journal of Graph Theory 95.1 (2020), 125–13
Igor Fabrici, Jochen Harant, Tomáš Madaras, Samuel Mohr, Roman Soták, Carol T. Zamfirescu
(See online at https://doi.org/10.1002/jgt.22542) - Rooted structures in graphs: a project on Hadwiger’s conjecture, rooted minors, and Tutte cycles, Dissertation, Ilmenau (2020)
Samuel Mohr
- A construction of uniquely colourable graphs, erscheint in Discrete Applied Mathematics (2021)
Samuel Mohr
(See online at https://doi.org/10.1016/j.dam.2020.11.015) - Kempe chains and rooted minors
Matthias Kriesell, Samuel Mohr
(See online at https://doi.org/10.48550/arXiv.1911.09998) - Rooted Minors and Locally Spanning Subgraphs
Thomas Bohme, Jochen Harant, Matthias Kriesell, Samuel Mohr, Jens M. Schmidt
(See online at https://doi.org/10.48550/arXiv.2003.04011)
