A famous (widely open) conjecture of Hadwiger states that every K_{k+1}-minor-free graph is k-colorable. Kempe chains are one of the basic tools used in the proofs of variations on this conjecture. Thus, it is important to understand what the existence of particular Kempe chains guarantees in terms of the existence of (rooted) minors. In this thesis, we survey the known results on this topic and try to generalize them.
Seznam odborné literatury
M. Kriesell, S. Mohr: Kempe Chains and Rooted Minors, preprint, 2022
A. Martinsson, Raphael Steiner: Strengthening Hadwiger's conjecture for 4-and 5-chromatic graphs, Journal of Combinatorial Theory, Series B 164 (2024), 1-16.
- zadáno a potvrzeno stud. odd.