2021/02/20 by Jacob Fox, Zoe Himwich, Fox, Jacob +3
Computer Science · Mathematics · #05C35 #05C38 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2102.10220
openalex publication_date 2021/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the following question: how few edges can we delete from any H-free graph on n vertices in order to make the resulting graph k-colorable? It turns out that various classical problems in extremal graph theory are special cases of this question. For H any fixed odd cycle, we determine the answer up to a constant factor when n is sufficiently large. We also prove an upper bound when H is a fixed clique that we conjecture is tight up to a constant factor, and prove upper bounds for more general families of graphs. We apply our results to get a new bound on the maximum cut of graphs with a forbidden odd cycle in terms of the number of edges.