Additive approximation algorithms for list-coloring minor-closed class of graphs

摘要

It is known that computing the list chromatic number is harder than computing the chromatic number (assuming NP ≠ coNP). In fact, the problem of deciding whether a given graph is f-list-colorable for a function f: V → {c -1, c} for c ≥ 3 is Πp2-complete. In general, it is believed that approximating list coloring is hard for dense graphs.