2025/09/08 by Michael Lafferty, Runrun Liu, Lafferty, Michael +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2509.07144
openalex publication_date 2025/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Contraction-critical graphs came from the study of minimal counterexamples to Hadwiger's conjecture. A graph is k-contraction-critical if it is k-chromatic, but any proper minor is (k-1)-colorable. It is a long-standing result of Mader that k-contraction-critical graphs are 7-connected for k≥7. In this paper, we provide the improvement of Mader's result for small values of k. We show that k-contraction-critical graphs are 8-connected for k≥17, 9-connected for k≥29, and 10-connected for k≥41. As a corollary of one of our intermediate results, we also prove that every 30-connected graph is 4-linked.