Improved Inapproximability Results for Maximum k-Colorable Subgraph

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-\frac{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

$\approx 1-\frac{1}{33 k}$

of edges. Previously, only a hardness factor of

$1- O\bigl(\frac{1}{k^2}\bigr)$

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

$\frac{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.