Paperlane

no. 5 · Friday 30 October 2026

Minimum-degree thresholds beyond bounded colourability

Xinqi Huang and Hong Liu

math.CO

Abstract

We survey recent developments on minimum-degree thresholds in extremal graph theory, with an emphasis on structural refinements of the chromatic-threshold problem. The chromatic threshold asks when a linear minimum-degree condition forces bounded chromatic number in an \(H\)-free graph; its complete classification shows a striking finite trichotomy. We discuss several stronger and related threshold notions in which bounded colourability is replaced by bounded \(H\)-free homomorphic images, bounded neighbourhood complexity via VC-dimension, exact blowup structure for maximal \(H\)-free graphs, and improved quantitative bounds in graph removal lemmas. In contrast with the rigidity of the chromatic threshold, these newer parameters exhibit richer behaviour, including separations from \(δ_χ(H)\), new exact values, accumulation points in fixed-chromatic spectra, positivity phenomena for 3-chromatic graphs, asymmetric variants, and failures of monotonicity.

comments
Survey article. Accepted for publication in the Proceedings of the International Consortium of Chinese Mathematicians (ICCM 2025)
fields
Combinatorics
pdf ↗ page arXiv:2610.39759 ↗