Proof of Thomassen's Conjecture on Highly connected subgraphs with large chromatic number
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917458563039232 |
|---|---|
| author | Polavarapu, Achintya Raya |
| author_facet | Polavarapu, Achintya Raya |
| contents | For integers $k\ge 1$ and $m\ge 2$, let $g(k,m)$ be the least integer $n\ge 1$ such that every graph with chromatic number at least $n$ contains a $(k+1)$-connected subgraph with chromatic number at least $m$. We prove that \[
g(k,m)\le \max(m+2k-2,\,3k+1) \] for all $k\ge 1$ and $m\ge 2$, establishing the 1983 conjecture of Thomassen that $g(k,k+1)\le 3k+1$. The key new ingredient is a Hall-feasibility argument replacing the final numerical step in the proof of Nguyen. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02543 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Proof of Thomassen's Conjecture on Highly connected subgraphs with large chromatic number Polavarapu, Achintya Raya Combinatorics Primary 05C15, Secondary 05C35, 05C40, 05C70 For integers $k\ge 1$ and $m\ge 2$, let $g(k,m)$ be the least integer $n\ge 1$ such that every graph with chromatic number at least $n$ contains a $(k+1)$-connected subgraph with chromatic number at least $m$. We prove that \[ g(k,m)\le \max(m+2k-2,\,3k+1) \] for all $k\ge 1$ and $m\ge 2$, establishing the 1983 conjecture of Thomassen that $g(k,k+1)\le 3k+1$. The key new ingredient is a Hall-feasibility argument replacing the final numerical step in the proof of Nguyen. |
| title | Proof of Thomassen's Conjecture on Highly connected subgraphs with large chromatic number |
| topic | Combinatorics Primary 05C15, Secondary 05C35, 05C40, 05C70 |
| url | https://arxiv.org/abs/2605.02543 |