On cuts of small chromatic number in sparse 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_ | 1866908573360979968 |
|---|---|
| author | Aubian, Guillaume Bonamy, Marthe Bourneuf, Romain Fontaine, Oscar Picasarri-Arrieta, Lucas |
| author_facet | Aubian, Guillaume Bonamy, Marthe Bourneuf, Romain Fontaine, Oscar Picasarri-Arrieta, Lucas |
| contents | For a given integer $k$, let $\ell_k$ denote the supremum $\ell$ such that every sufficiently large graph $G$ with average degree less than $2\ell$ admits a separator $X \subseteq V(G)$ for which $χ(G[X]) < k$. Motivated by the values of $\ell_1$, $\ell_2$ and $\ell_3$, a natural conjecture suggests that $\ell_k = k$ for all $k$. We prove that this conjecture fails dramatically: asymptotically, the trivial lower bound $\ell_k \geq \tfrac{k}{2}$ is tight. More precisely, we prove that for every $\varepsilon>0$ and all sufficiently large $k$, we have $\ell_k \leq (1+\varepsilon)\tfrac{k}{2}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01791 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On cuts of small chromatic number in sparse graphs Aubian, Guillaume Bonamy, Marthe Bourneuf, Romain Fontaine, Oscar Picasarri-Arrieta, Lucas Combinatorics Discrete Mathematics For a given integer $k$, let $\ell_k$ denote the supremum $\ell$ such that every sufficiently large graph $G$ with average degree less than $2\ell$ admits a separator $X \subseteq V(G)$ for which $χ(G[X]) < k$. Motivated by the values of $\ell_1$, $\ell_2$ and $\ell_3$, a natural conjecture suggests that $\ell_k = k$ for all $k$. We prove that this conjecture fails dramatically: asymptotically, the trivial lower bound $\ell_k \geq \tfrac{k}{2}$ is tight. More precisely, we prove that for every $\varepsilon>0$ and all sufficiently large $k$, we have $\ell_k \leq (1+\varepsilon)\tfrac{k}{2}$. |
| title | On cuts of small chromatic number in sparse graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2510.01791 |