pipette
ENEnglish

Minimum-degree thresholds beyond bounded colourability

Xinqi Huang, Hong Liu

Preprint

En palabras de los autores

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 \(\delta_\chi(H)\), new exact values, accumulation points in fixed-chromatic spectra, positivity phenomena for 3-chromatic graphs, asymmetric variants, and failures of monotonicity.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Survey article. Accepted for publication in the Proceedings of the International Consortium of Chinese Mathematicians (ICCM 2025)