Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's Conjecture
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913177960185856 |
|---|---|
| author | Kawarabayashi, Ken-ichi Yu, Gexin |
| author_facet | Kawarabayashi, Ken-ichi Yu, Gexin |
| contents | For a given subset $S\subseteq V(G)$ of a graph $G$, the pair $(G,S)$ is \emph{knitted} if for every partition of $S$ into non-empty subsets $S_1, S_2, \ldots, S_t$, there exist pairwise disjoint connected subgraphs $C_1, C_2, \ldots, C_t$ in $G$ such that $S_i\subseteq V(C_i)$ for all $1 \le i \le t$. A graph $G$ is \emph{$\ell$-knitted} if $(G,S)$ is knitted for every subset $S\subseteq V(G)$ of size $\ell$. In this paper, we prove that every $8\ell$-connected graph is $\ell$-knitted. We subsequently apply this result to Hadwiger's Conjecture, which states that every $k$-chromatic graph contains a $K_k$-minor. Specifically, we demonstrate that the vertex connectivity of any minimal counterexample to Hadwiger's Conjecture is at least $\lceil k/8 \rceil$, improving upon the previous lower bound of $\lceil 2k/27 \rceil$ established by Kawarabayashi (2007). Our proof corrects a gap in the argument of Kawarabayashi-Yu~(2013) and establishes the claim stated without proof in Liu--Rolek--Yu~(2019). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_01586 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's Conjecture Kawarabayashi, Ken-ichi Yu, Gexin Combinatorics For a given subset $S\subseteq V(G)$ of a graph $G$, the pair $(G,S)$ is \emph{knitted} if for every partition of $S$ into non-empty subsets $S_1, S_2, \ldots, S_t$, there exist pairwise disjoint connected subgraphs $C_1, C_2, \ldots, C_t$ in $G$ such that $S_i\subseteq V(C_i)$ for all $1 \le i \le t$. A graph $G$ is \emph{$\ell$-knitted} if $(G,S)$ is knitted for every subset $S\subseteq V(G)$ of size $\ell$. In this paper, we prove that every $8\ell$-connected graph is $\ell$-knitted. We subsequently apply this result to Hadwiger's Conjecture, which states that every $k$-chromatic graph contains a $K_k$-minor. Specifically, we demonstrate that the vertex connectivity of any minimal counterexample to Hadwiger's Conjecture is at least $\lceil k/8 \rceil$, improving upon the previous lower bound of $\lceil 2k/27 \rceil$ established by Kawarabayashi (2007). Our proof corrects a gap in the argument of Kawarabayashi-Yu~(2013) and establishes the claim stated without proof in Liu--Rolek--Yu~(2019). |
| title | Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's Conjecture |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2606.01586 |