Sparse graph cut chromatic threshold

Conjecture 1.3 · arXiv:2510.01791

arXiv Conjecture high confidence— first stated 2025-10-02

Authors: Guillaume Aubian, Marthe Bonamy, Romain Bourneuf, Oscar Fontaine, Lucas Picasarri-Arrieta

Status disproved high confidence

Conjecture 1.3 is disproved in the same paper that states it. The authors prove that the conjecture 'fails dramatically': whereas Conjecture 1.3 asserts ℓ_k = k for all k, the paper establishes that for every ε > 0 and all sufficiently large k, ℓ_k ≤ (1+ε)k/2, showing that the trivial lower bound ℓ_k ≥ k/2 is asymptotically tight. The paper is to appear in Discrete Mathematics. No subsequent follow-up papers addressing Conjecture 1.3 were found in the indexed literature.

Reviewer notes. The conjecture is disproved within the source paper itself (arXiv:2510.01791). The paper proposes Conjecture 1.3 as the natural bold generalization of the confirmed cases ℓ_1=1, ℓ_2=2 and the conjectured ℓ_3=3, and then proves it is far from correct by showing ℓ_k ≤ (1+ε)k/2 asymptotically. No external follow-up papers were found; the disproof is complete and contained in the source paper.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every integer $k$ and every graph $G$ on at least $k$ vertices, if $$|E(G)|<k|V(G)|-\tfrac{k(k+1)}{2},$$ then $G$ admits a cut $X$ with $\chi(G[X])<k$. In particular, $\ell_{k}=k$.

Context

Motivated by the confirmed cases $\ell_1=1$, $\ell_2=2$ (Theorem 1.1), and the conjectured $\ell_3=3$ (Conjecture 1.2), the paper's authors propose this bold generalization asserting that $\ell_k=k$ for all $k$. The main purpose of the paper is then to show that this conjecture is far from correct.

Notes. This conjecture is introduced by the paper's own authors and immediately refuted within the same paper: Theorem 1.4 shows $\ell_k \leq (1+\varepsilon)\frac{k}{2}$ for all sufficiently large $k$, so that asymptotically $\ell_k \sim \frac{k}{2}$ rather than $\ell_k = k$.

Source paper

On cuts of small chromatic number in sparse graphs
Guillaume Aubian, Marthe Bonamy, Romain Bourneuf, Oscar Fontaine, Lucas Picasarri-Arrieta · 2025-10-02
https://arxiv.org/abs/2510.01791