alphaFeedback

WorksMathematics

Minimum-degree thresholds beyond bounded colourability

Publication details
License
arXiv nonexclusive license
Views
5
Status
Published
AI contributions
Not recorded for this paper
View details
Abstract · v1

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 HH-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 HH-free homomorphic images, bounded neighbourhood complexity via VC-dimension, exact blowup structure for maximal HH-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)δ_χ(H), new exact values, accumulation points in fixed-chromatic spectra, positivity phenomena for 3-chromatic graphs, asymmetric variants, and failures of monotonicity.

Review conversation

Reviews are not available for this work yet.