On cuts of small chromatic number in sparse graphs
October 02, 2025
Abstract
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 \(\chi(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 \geqslant\tfrac{k}{2}\) is tight. More precisely, we prove that for every \(\varepsilon>0\) and all sufficiently large \(k\), we have \(\ell_k \leqslant(1+\varepsilon)\tfrac{k}{2}\).
1 Introduction↩︎
For a given integer \(k\), we define \(\ell_k\) as the supremum \(\ell\) such that every sufficiently large2 graph \(G\) with average degree less than \(2\ell\) contains a set \(X \subseteq V(G)\) with the properties that \(G \setminus X\) is disconnected and \(\chi(G[X])<k\).
Observe first that any graph with average degree less than \(k\) and order at least \(k+1\) contains a vertex of degree at most \(k-1\), whose neighbourhood is thus a separator of chromatic number less than \(k\). Conversely, for any \(n \geqslant k\), one can construct an \(n\)-vertex graph with no such set \(X\) by taking a clique on \(k\) vertices and joining it completely to an independent set of size \(n-k\), see 1 for an illustration. This graph has exactly \(kn - \tfrac{k(k+1)}{2}\) edges and hence average degree less than \(2k\), yet every separator must include the entire clique, which has chromatic number \(k\). This shows that \(\ell_k\) is well-defined and satisfies \[\frac{k}{2} \;\leqslant\; \ell_k \;\leqslant\; k.\]
Having established general bounds, let us now consider the small cases. It is folklore that \(\ell_1 = 1\): indeed, whenever \(n \geqslant 2\), every \(n\)-vertex graph with fewer than \(n-1\) edges is disconnected, while connected graphs with average degree \(2\) certainly exist (e.g. cycles).
The case \(k=2\) was resolved by Chen and Yu [1], confirming a conjecture of Caro with a very elegant inductive proof.
Theorem 1 ([1]). Any graph on \(n\) vertices with fewer than \(2n-3\) edges admits a stable cut, while some graphs with exactly \(2n-3\) edges do not. In particular, \(\ell_2=2\).
The extremal graphs with \(2n-3\) edges and no stable cut were first characterized by Le and Pfender [2], although their proof contained a gap later filled by Rauch and Rautenbach [3].
The next case, \(k=3\), was investigated by Bogdanov, Neustroeva, Sokolov, Volostnov, Russkin, and Voronov [4], who formulated the following conjecture.
Any \(n\)-vertex graph with fewer than \(3n-6\) edges admits a bipartite cut, while some graphs with \(3n-6\) edges do not. In particular, \(\ell_3=3\).
The extremal examples here are provided by \(3\)-trees. In fact, an even stronger conjecture predates this one, namely that under the same conditions one can always find a cut inducing a forest [5]. Partial progress was obtained in the same paper by Chernyshev, Rauch and Rautenbach, who proved that every \(n\)-vertex graph with fewer than \(\tfrac{11}{5}n-\tfrac{18}{5}\) edges admits a forest cut. This bound was subsequently improved to \(\tfrac{9}{4}n-\tfrac{15}{4}\) by Botler, Couto, Fernandes, de Figueiredo, Gómez, dos Santos and Sato [6], and then to \(\tfrac{19}{8}n-\tfrac{28}{8}\) by Bogdanov et al. [4]. In the same work, the authors also established a bound of \(\tfrac{80}{31}n-\tfrac{134}{31}\) for bipartite cuts. Related results were later obtained by Cheng, Tang and Zhan [7].
Taken together, these cases naturally suggest a bold generalization:
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\).
The main purpose of this note is to show that [conj:bold] is in fact far from correct.
theoremmain For any \(\varepsilon>0\) and all sufficiently large \(k\), we have \[\ell_k \leqslant(1+\varepsilon)\,\tfrac{k}{2}.\]
While this does not fully determine \(\ell_k\), it provides an essentially sharp asymptotic estimate when combined with the lower bound: \[\tfrac{k}{2} \leqslant\ell_k \leqslant(1+o(1))\tfrac{k}{2}\]
Thus we arrive at the following conclusion.
Theorem 2. As \(k\) grows large, we have \(\ell_k \sim \frac{k}{2}\).
In fact, we prove a stronger statement:
Theorem 3. For every integer \(k\), there exist arbitrarily large graphs with average degree \({(1 + o(1))k}\) in which every separator contains a clique of size \(k\).
This construction is interesting in its own right, and appeared in [8] where it was used to establish lower bounds on the smallest maximum degree of a cut (instead of its chromatic number). Since the chromatic number is always at most the degeneracy plus one, [th:main] also rules out the strengthening of [conj:bold] where \(\chi(G[X])<k\) is replaced by the requirement that \(G[X]\) be \((k-2)\)-degenerate. This would have tied in neatly with the already studied cases:
the only 1-degenerate graph is the empty one,
a \(0\)-degenerate graph is stable,
a \(1\)-degenerate graph is a forest.
Thus, for \(k=1,2\), this is equivalent to the standard definition using chromatic number, while with \(k=3\) we retrieve the well-studied notion of forest-cuts. We note that the condition \(\chi(G[X])<k\) seems easier to work with when attempting to obtain positive results, as it is compatible with identifying a stable set into a single vertex3.
2 Proofs↩︎
In a bipartite graph \(G = (A \cup B, E)\), a bi-hole of size \(k\) is a pair \((A', B')\) with \(\min\{|A'|,|B'|\} = k\), \(A' \subseteq A\), \(B' \subseteq B\), such that there is no edge between \(A'\) and \(B'\). In some sense, the size of a largest bi-hole in a bipartite graph corresponds to the “bipartite independence number” of that graph. Axenovich, Sereni, Snyder, and Weber [9] studied the following question: what is the largest integer \(f(n, \Delta)\) such that every \(n \times n\) bipartite graph \(G = (A \cup B, E)\) with \(\deg(a) \leqslant\Delta\) for every vertex \(a \in A\) contains a bi-hole of size \(f(n, \Delta)\)? They proved that the asymptotic behaviour of the function \(f(n, \Delta)\) is \(\Theta\left(\frac{\ln\Delta}{\Delta} \cdot n\right)\). We make use of the following upper bound.
Theorem 4 ([9]). Let \(\Delta \geqslant 27\) be an integer and \(n \geqslant\frac{\Delta}{\ln\Delta}\). Then, there exists an \(n \times n\) bipartite graph \(G = (A \cup B, E)\) with \(\deg(a) \leqslant\Delta\) for every vertex \(a \in A\), which contains no bi-hole of size at least \(8 \cdot \frac{\ln\Delta}{\Delta} \cdot n\).
Such a graph can be obtained with high probability from a random bipartite graph \(G(2n, 2n, \Delta/(4n))\) by restricting one part to \(n\) vertices of degree at most \(\Delta\) and the other part to any set of \(n\) vertices.
We now prove [th:main], which we restate for convenience.
Proof. Fix \(\varepsilon > 0\), set \(\eta \mathrel{\vcenter{:}}= \varepsilon/2\) and let \(\Delta \geqslant 27\) be large enough so that \(1 - 8 \cdot \frac{\ln\Delta}{\Delta} \geqslant\frac{1}{1+\eta}\). Let \(k\) be an integer large enough so that \(\eta k \geqslant 2\Delta\) and \((1+\eta) k \geqslant\frac{\Delta}{\ln\Delta}\). Set \(\ell \mathrel{\vcenter{:}}= (1+\varepsilon) \frac{k}{2}\). To show that \(\ell_k \leqslant\ell\), it suffices to prove that there exist arbitrarily large graphs \(G\) with average degree less than \(2\ell\) and where every separator \(X \subseteq V(G)\) of \(G\) satisfies \(\chi(G[X]) \geqslant k\).
Set \(\alpha \mathrel{\vcenter{:}}= \lceil(1+\eta) k\rceil \geqslant\frac{\Delta}{\ln\Delta}\), and let \(\beta \geqslant 2\) be an integer. By 4, there exists an \(\alpha \times \alpha\) bipartite graph \(H = (A \cup B, E)\) with \(\deg(a) \leqslant\Delta\) for every vertex \(a \in A\), which contains no bi-hole of size at least \(8 \cdot \frac{\ln\Delta}{\Delta} \cdot \alpha\). Consider the graph \(G\) whose vertex set is the union of \(\beta\) pairwise disjoint sets \(A_1, \ldots, A_\beta\) of \(\alpha\) vertices each, and whose edges are exactly such that:
for every \(i \in [1,\beta]\), the graph \(G[A_i]\) is a clique, and
for every \(i \in [1,\beta-1]\), the semi-induced subgraph \(G[A_i, A_{i+1}]\) is isomorphic to \(H\), with \(A_i\) mapped to the part \(A\) of \(H\) and \(A_{i+1}\) to the part \(B\) of \(H\).
Every separator \(X \subseteq V(G)\) of \(G\) satisfies \(\chi(G[X]) \geqslant k\).
Proof. Consider a set \(X \subseteq V(G)\) such that \(G \setminus X\) is disconnected. Since each \(G[A_i]\) is a clique, there exists an integer \(i \in [1,\beta-1]\) such that there is no edge in \(G\) between \(A_i \setminus X\) and \(A_{i+1} \setminus X\). By construction of \(G\), this means that \((A_i \setminus X, A_{i+1} \setminus X)\) is a bi-hole in \(G[A_i, A_{i+1}] \cong H\). Therefore, by definition of \(H\), we have \[\min\{|A_i \setminus X|, |A_{i+1} \setminus X|\} \leqslant 8 \cdot \frac{\ln\Delta}{\Delta} \cdot \alpha.\] Thus, we have \[\max\{|A_i \cap X|, |A_{i+1} \cap X|\} \geqslant\alpha\left(1-8 \cdot \frac{\ln\Delta}{\Delta}\right).\] Since \(G[A_i]\) and \(G[A_{i+1}]\) are cliques, we deduce \[{\chi(G[X]) \geqslant\alpha\left(1-8 \cdot \frac{\ln\Delta}{\Delta}\right) \geqslant(1 + \eta) k \cdot \frac{1}{1+\eta} \geqslant k}.\qedhere\] ◻
\(G\) has average degree less than \(2\ell\).
Proof. In \(H\), every vertex \(a \in A\) satisfies \(\deg(a) \leqslant\Delta\), so \(H\) has at most \(\alpha \Delta\) edges. Therefore, \[|E(G)| \leqslant\beta \left(\frac{\alpha(\alpha-1)}{2} + \alpha \Delta\right).\] Moreover \(|V(G)|=\beta\alpha\). Thus, the average degree of \(G\) is \[\frac{2|E(G)|}{|V(G)|} \leqslant\alpha - 1+ 2\Delta < (1 +2\eta) k = (1+\varepsilon) k = 2\ell.\] ◻
Since \(G\) can be made arbitrarily large by choosing appropriately the value of \(\beta\), the two claims conclude the proof. ◻
In the above proof, we can take \(\Delta = \Theta\left(\frac{1}{\varepsilon}\ln\frac{1}{\varepsilon}\right)\) and \(k = \Theta\left(\frac{1}{\varepsilon^2}\ln\frac{1}{\varepsilon}\right)\).
3 Conclusion↩︎
We disproved [conj:bold] in a strong form, but only for very large \(k\). It would be interesting to establish the smallest \(k\) for which [conj:bold] strays from the truth, especially if it turns out to be already at \(k=3\). It also seems reasonable to believe that the stronger form, requiring a cut to be not only \((k-1)\)-colourable but in fact \((k-2)\)-degenerate, would break down earlier, maybe indeed for \(k=3\).
References↩︎
Research supported by JST as part of ASPIRE, Grant Number JPMJAP2302.↩︎
As a function of \(k\) and \(\ell\).↩︎
For any smallest graph \(G\) with \(\ell |V(G)|-|E(G)|>c\) and no cut of chromatic number less than \(k\), we obtain that every subset \(X\) of vertices is either a clique or satisfies \(\ell |X|-|E(G[X])|>\ell t - \frac{t(t-1)}{2}\), where \(t=\chi(G[X])\).↩︎