We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a k-colorable graph with k colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random k-coloring properly colors an expected fraction 1-1/k of edges. We prove that given a graph promised to be k-colorable, it is NP-hard to find a k-coloring that properly colors more than a fraction 1-1/(33 k) of edges. Previously, only a hardness factor of 1- O(1/k^2) was known. Our result pins down the correct asymptotic dependence of the approximation factor on k. Along the way, we prove that approximating the Maximum 3-colorable subgraph problem within a factor greater than 32/33 is NP-hard.

Using semidefinite programming, it is known that one can do better than a random coloring and properly color a fraction 1-\frac{1}{k} +\frac{2 \ln k}{k^2} of edges in polynomial time. We show that, assuming the 2-to-1 conjecture, it is hard to properly color
(using k colors) more than a fraction 1-\frac{1}{k} + O\left(\frac{\ln k}{k^2}\right) of edges of a k-colorable graph.

This is essentially the version that appeared in APPROX 2009, with the conditional hardness result based on the 2-to-1 conjecture. The earlier ECCC version *incorrectly* claimed an extension of the hardness result from d-to-1 conjecture for d larger than 2. This version reverts back to assuming the stronger 2-to-1 conjecture.

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a k-colorable graph with k colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random k-coloring properly colors an expected fraction 1-1/k of edges. We prove that given a graph promised to be k-colorable, it is NP-hard to find a k-coloring that properly colors more than a fraction 1-1/(33 k) of edges. Previously, only a hardness factor of 1- O(1/k^2) was known. Our result pins down the correct asymptotic dependence of the approximation factor on k. Along the way, we prove that approximating the Maximum 3-colorable subgraph problem within a factor greater than 32/33 is NP-hard.

Using semidefinite programming, it is known that one can do better than a random coloring and properly color a fraction 1-1/k + 2 \ln k/k^2 of edges in polynomial time. We show that, assuming the d-to-1 conjecture, it is hard to properly color (using k colors) more than a fraction 1-1/k+ O(d^{3/2} \ln k/k^2) of edges of a k-colorable graph.