It is well known that both vertex coloring and maximum independent set are very hard to approximate in polynomial time under standard complexity assumptions. Given a black-box hardness of independent set, I am interested in obtaining a hardness result for coloring. This question can be considered for specific graph classes.

Question: Let $C$ be a family of graphs such that there is no $a$-approximation for the maximum independent set problem for graphs in $C$. What is the best approximation possible for vertex coloring for graphs in $C$?

Note that the converse direction is easier. Given an $a$-approximation algorithm for max-independent set we can get an $a*log(n)$-approximation for coloring based on greedily finding independent sets (if $C$ is closed under removing subsets of vertices).

  • 1
    $\begingroup$ Possibility related: for random graphs, apparently the maximum independent sets (w.h.p.) are easier to characterize than the min colorings.. See e.g. doi.org/10.1007/BF01874388 . $\endgroup$
    – Neal Young
    Jan 28 at 22:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.