Connectivity of contraction-critical graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914027925405696 |
|---|---|
| author | Lafferty, Michael Liu, Runrun Rolek, Martin Yu, Gexin |
| author_facet | Lafferty, Michael Liu, Runrun Rolek, Martin Yu, Gexin |
| contents | 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\ge7$. 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\ge17$, $9$-connected for $k\ge29$, and $10$-connected for $k\ge41$. As a corollary of one of our intermediate results, we also prove that every $30$-connected graph is $4$-linked. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_07144 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Connectivity of contraction-critical graphs Lafferty, Michael Liu, Runrun Rolek, Martin Yu, Gexin Combinatorics 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\ge7$. 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\ge17$, $9$-connected for $k\ge29$, and $10$-connected for $k\ge41$. As a corollary of one of our intermediate results, we also prove that every $30$-connected graph is $4$-linked. |
| title | Connectivity of contraction-critical graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.07144 |