Rooted complete minors in line graphs with a Kempe coloring (Q1741595): Difference between revisions

Motivated by \textit{H. Hadwiger}'s conjecture [Vierteljahresschr. Naturforsch. Ges. Zürich 88, 133--142 (1943; Zbl 0061.41308)] the first author of this article stated a related conjecture [J. Graph Theory 85, No. 1, 207--216 (2017; Zbl 1368.05052)] about forcing clique minors via certain colourability assumptions. However, on the one hand more restrictive types of colourings are used in the statement of this conjecture, but on the other hand this allows to prescribe certain vertices to occur in the branch sets of the clique minor. In order to state the conjecture, some definitions have to be given first. A proper vertex-colouring of a graph is called a Kempe colouring if the union of any two colour classes induces a connected subgraph. Given a set \(\mathcal{C}\) of pairwise disjoint non-empty sets, we call a set \(T\) a transversal for \(\mathcal{C}\) if \(|T \cap C| = 1\) holds for every \(C \in \mathcal{C}\). Conjecture. Let \(G\) be a graph and \(\mathcal{C}\) be the set of colour classes of any Kempe colouring of \(G\). Then for every transversal \(T\) for \(\mathcal{C}\) there exists a clique minor \(M\) in \(G\) such that \(T\) is also a transversal for the set of branch sets of \(M\). In this article, conjecture 1 is confirmed for line graphs. Theorem. Let \(L\) be a line graph and \(\mathcal{C}\) be the set of colour classes of any Kempe colouring of \(L\). Then for every transversal \(T\) for \(\mathcal{C}\) there exists a clique minor \(M\) in \(L\) such that \(T\) is also a transversal for the set of branch sets of \(M\). The statement of theorem 2 is first translated to a statement about edges in usual graphs. The proof of the translated statement works via induction on the number of edges in the graph and distinguishes two cases: depending on the number \(k\) of colour classes in the given edge-colouring, either a vertex of degree \(k\) exists or all vertices have degree less than~\(k\). In the first case, Menger's theorem is a key ingredient of the proof. The second case reduces the statement to graphs being cliques, for which a proof is given separately.