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

CREATORKen-ichi Kawarabayashi, Gexin Yu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.01586

Browse the full library · About the Tower of Babel