Hardness of finding large independent sets in three-colorable graphs

Abstract — v1

We prove that, for every fixed $0\lt \delta\lt 1/3$, it is NP-hard to distinguish three-colorable graphs from graphs in which every independent set has fewer than δ times the number of vertices. Consequently, for every fixed integer c ≥ 3, finding a proper c-coloring of a three-colorable graph is NP-hard.