Making an H H‐free graph k k‐colorable. Issue 2 (16th August 2022) - Fox, Jacob; Himwich, Zoe; Mani, Nitya
Abstract: We study the following question: How few edges can we delete from any H H ‐free graph on n n vertices to make the resulting graph k k ‐colorable? It turns out that various classical problems in extremal graph theory are special cases of this question. For H H any fixed odd cycle, we determine the answer up to a constant factor when n n is sufficiently large. We also prove an upper bound when H 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.