Theory of Computing ------------------- Title : Improved Inapproximability Results for Maximum $k$-Colorable Subgraph Authors : Venkatesan Guruswami and Ali Kemal Sinop Volume : 9 Number : 11 Pages : 413-435 URL : https://theoryofcomputing.org/articles/v009a011 Abstract -------- $\newcommand{\E}{\mathbb{E}}%_{#1}\left[#2\right]} \newcommand{\expct}[2]{\mathbb{E}_{#1}\left[#2\right]} \newcommand{\prob}[2]{\mathsf{Pr}_{#1}\left[#2\right]} \newcommand{\var}[2]{\mathsf{Var}_{#1}\left[#2\right]} \newcommand{\cov}[1]{\mathsf{Cov}\left[#1\right]} \newcommand{\threehardness}{33}$ 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 $\approx 1- 1/(33k)$ 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 $2$-to-$1$ conjecture, it is hard to properly color (using $k$ colors) more than a fraction $1- 1/k + O(\ln k/k^2)$ of edges of a $k$-colorable graph. An extended abstract of this paper appeared in the Proceedings of the 12th International Workshop on Approximation, Randomization, and Combinatorial Optimization, 2009.