The graph coloring problem, in which we have to decide whether a given graph can be legally colored using $K$ colors, is NP-complete for any $K>2$.

Consider the following more restricted variant of the problem:

Given a graph with $N^2$ nodes in which each node has degree at most $2N$. Provided that we can color the given graph instance with $N$ colors.

What is the best approximation or inapproximation bound known for this version of the graph coloring problem (in polynomial or superpolynomial time)?

  • 3
    $\begingroup$ Your problem is a decision problem rather than an optimization problem, so I'm not sure what you mean by "approximation". $\endgroup$ – Yuval Filmus Jun 18 '17 at 13:47
  • $\begingroup$ Agreed. Modifying it to the decision version. $\endgroup$ – J.Doe Jun 18 '17 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.