Connectivities for k k -knitted graphs and for minimal counterexamples to Hadwiger’s Conjecture
Ken-ichi Kawarabayashi, Gexin Yu · 2026
Read Connectivities for k k -knitted graphs and for minimal counterexamples to Hadwiger’s Conjecture by Ken-ichi Kawarabayashi, Gexin Yu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-01586.txt.
Description
Kawarabayashi and Yu prove connectivity bounds for knitted graphs. A pair (G, S) is knitted if each split of S can be honored. For any partition of S into nonempty parts, disjoint connected subgraphs must cover them. A graph is l-knitted if this holds for every S of size l. They prove every 8l-connected graph is l-knitted. The result then feeds into Hadwiger's Conjecture. That conjecture says every k-chromatic graph contains a K_k minor.
They bound the vertex connectivity of any minimal counterexample. It is at least the ceiling of k over 8. This improves the prior bound of ceiling of 2k over 27. Their proof also corrects a gap in a 2013 argument. A claim stated without proof in 2019 is now established.
Catalog record
| CREATOR | Ken-ichi Kawarabayashi, Gexin Yu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.01586