Making an H $H$‐free graph k $k$‐colorable. Issue 2 (16th August 2022)

• Record Type: Journal Article
• Authors: Fox, Jacob; Himwich, Zoe; Mani, Nitya
• Is Part Of: Journal of graph theory. Volume 102:Issue 2(2023)
• Page Start: 234
• Page End: 261
• Publication Date: 2022-08-16
• Subjects: extremal graph theory -- forbidden subgraph -- max‐cut; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22868
• Languages: English
• ISSNs: 0364-9024

Abstract

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.