Additive chromatic approximation gap in K_k-minor-free
Open question: better additive approximation for $K_{4k_0+1}$-minor-free graphs · arXiv:1707.03888
Status open high confidence
The question of whether the additive approximation gap for chromatic number of $K_{4k_0+1}$-minor-free graphs can be tightened remains open. The source paper (arXiv:1707.03888, ICALP 2018, J. Combin. Theory Ser. B 2020) establishes a hardness lower bound showing no poly-time algorithm achieves additive error below $k_0/4$, while Kawarabayashi et al.'s prior algorithm achieves additive error $k_0-2$, leaving a gap of roughly a factor of 4. No subsequent work narrowing this gap was found in the indexed literature.
Reviewer notes. No follow-up resolving the approximation gap between $k_0/4$ and $k_0-2$ was found in the indexed literature. The paper appeared as ICALP 2018 (LIPIcs) and was later published in J. Combin. Theory Ser. B (2020, doi:10.1016/j.jctb.2020.02.001); these are the same work and do not constitute follow-up. The conjecture is now approximately 8 years old with no known progress on closing the factor-of-4 gap.
Context
Kawarabayashi et al. showed the chromatic number of $K_k$-minor-free graphs can be approximated additively up to $k-2$. Corollary 4 of this paper establishes that an additive error of $k_0 - 1$ is NP-hard to achieve, leaving a gap of roughly a factor of 4 between the best known algorithm and the hardness bound.
Notes. PDF source; stated in prose as 'We leave open the question whether a better additive approximation (of course above the bound ≈ k/4 given by Corollary 4) is possible'.
Source paper
Additive non-approximability of chromatic number in proper minor-closed classes
Zdeněk Dvořák, Ken-ichi Kawarabayashi · 2017-07-12
https://arxiv.org/abs/1707.03888
PDF source