solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看815次
Additive non-approximability of chromatic number in proper minor-closed classes. (arXiv:1707.03888v1 [cs.DM])
来源于:arXiv
Robin Thomas asked whether for every proper minor-closed class C, there
exists a polynomial-time algorithm approximating the chromatic number of graphs
from C up to a constant additive error independent on the class C. We show this
is not the case: unless P=NP, for every integer k>=1, there is no
polynomial-time algorithm to color a K_{4k+1}-minor-free graph G using at most
chi(G)+k-1 colors. More generally, for every k>=1 and 1<=\beta<=4/3, there is
no polynomial-time algorithm to color a K_{4k+1}-minor-free graph G using less
than beta.chi(G)+(4-3beta)k colors. As far as we know, this is the first
non-trivial non-approximability result regarding the chromatic number in proper
minor-closed classes.
We also give somewhat weaker non-approximability bound for
K_{4k+1}-minor-free graphs with no cliques of size 4. On the positive side, we
present additive approximation algorithm whose error depends on the apex number
of the forbidden minor, and an algorithm with additive error 查看全文>>