Strengthening strong immersions with Kempe chains

2018/05/09 by Todd A. Gibson, Gibson, Todd A
Computer Science · #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1805.03729

Abstract

Every properly colored graph with χ(G)=k colors has edge-disjoint Kempe "backbones", Kempe chains anchored by color-critical vertices for each pair of colors. Certain color permutations arrange these backbones into a clique-like structure, a strengthening of strong immersions of complete graphs. This strengthened immersion is suggested as a template for identifying the disjoint subgraphs comprising Hadwiger's conjectured K_k minor present in k-chromatic graphs.

Related

• Immersions and Albertson's conjecture
• Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs
• On a recolouring version of Hadwiger's conjecture
• Forcing clique immersions through chromatic number
• Every graph with no K₈^-4 minor is 7-colorable