2026/07/30 by Xinqi Huang, Mingyuan Rong, Chong Shangguan
Mathematics · #math.CO #msc:05C15 #msc:05C35 #msc:05C60
19 pages, no figures
arxiv created 2026/07/30 · arxiv updated 2026/07/31
The chromatic threshold, originating in a question of Erdős and Simonovits, asks when a linear minimum-degree condition forces bounded chromatic number in H-free graphs. Motivated by a question of Thomassen, the homomorphism threshold asks for the stronger conclusion that every such graph admits a homomorphism to an H-free graph of bounded order. Since the work of Goddard and Lyle determined the clique case, exact homomorphism thresholds for individual non-complete forbidden graphs have remained unknown. In this paper, we extend the clique case to a larger family of forbidden graphs, determining the homomorphism threshold exactly for every graph in this family.