# Inapproximability bound for a variant of Graph Coloring Problem

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)?

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