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