Exact m(n,k) for H-free k-colorability
Open problem on $m(n,k)$ for fixed $k \geq 2$ · arXiv:2102.10220
Status open medium confidence
The open problem asks for the exact or asymptotic value of $m(n,k)$, the minimum number of edges to delete from any $n$-vertex graph to make it $k$-colorable, for any fixed $k \geq 2$. Fox, Himwich, and Mani proved the upper bound $m(n,k) \leq n^2/(ek)$ and noted that an Erd\H{o}s--R\'enyi random-graph lower bound is within 20% of this for large $k$, but stated explicitly that they have no idea what the exact or asymptotic value is. No follow-up paper resolving this specific question was found in five targeted web searches; the paper was subsequently published in the Journal of Graph Theory (2023, DOI 10.1002/jgt.22868) without any companion resolution of this problem.
Reviewer notes. The conjecture is ~5 years old; absence of follow-up after exhaustive search is plausible but not definitive for a hard quantitative extremal problem. The paper appeared in J. Graph Theory 102 (2023) 234–261, DOI 10.1002/jgt.22868, with no companion resolution. Internal reference 2105.03956 is a false positive (unrelated subject matter).
Context
The authors prove $m(n,k) \leq n^2/(ek)$ (Corollary 2.6) and derive a lower bound from an Erdős–Rényi random graph heuristic that is within 20% of this upper bound for large $k$. They state explicitly: 'We have no idea what the exact or asymptotic value of $m(n,k)$ is for any fixed $k \geq 2$.'
Notes. Stated as an informal open problem in the body of the paper without a labelled theorem environment.
Source paper
Making an $H$-Free Graph $k$-Colorable
Jacob Fox, Zoe Himwich, Nitya Mani · 2021-03-19
https://arxiv.org/abs/2102.10220
PDF source