On cuts of small chromatic number in sparse graphs
Abstract
For a given integer k , let ℓ k denote the supremum ℓ such that every sufficiently large graph G with average degree less than 2 ℓ admits a separator X ⊆ V ( G ) for which χ ( G [ X ] ) < k . Motivated by the values of ℓ 1 , ℓ 2 and ℓ 3 , a natural conjecture suggests that ℓ k = k for all k . We prove that this conjecture fails dramatically: asymptotically, the trivial lower bound ℓ k ⩾ k 2 is tight. More precisely, we prove that for every ε > 0 and all sufficiently large k , we have ℓ k ⩽ ( 1 + ε ) k 2 .
Fields of Study & Subjects
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Discrete Mathematics
- Volume
- 349
- Issue
- 6
- Pages
- 115052–115052
- Publication date
- 17 February 2026
- Language
- EN