Making an $H$-Free Graph $k$-Colorable

Jacob Fox, Zoe Himwich, Nitya Mani

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 c…