Near-Optimal Bounds for Testing k-Colorability

We study the sample complexity of testing $k$-colorability in the dense graph model. A graph is $\epsilon$-far from being $k$-colorable if at least $\epsilon n^2$ edge deletions are required to make it $k$-colorable. We prove that, for every integer $k\ge 2$, a uniformly random induced subgraph on $$O\text{\hspace{0.17em}⁣}\left(\frac{k\log k}{\epsilon }\right)$$ vertices is non-$k$-colorable with probability at least $2\mathrm{/}3$ whenever the original graph is $\epsilon$-far from $k$-colorable. The proof introduces a trial coloring process based on nested palette systems and iteratively selected pivots. This yields an upper bound of $O(k\log k\mathrm{/}\epsilon )$, which is no worse than the previous state of the art $O(k\log (1\mathrm{/}\epsilon )\mathrm{/}\epsilon )$ throughout the nonvacuous parameter range, and is an improvement whenever $1\mathrm{/}\epsilon$ is superpolynomial in $k$. Moreover, for every fixed $k$, our bound matches the known lower bound, thereby establishing the optimal $\mathrm{\Theta }(1\mathrm{/}\epsilon )$ dependence on $\epsilon$ and, to the best of our knowledge, achieving this optimal dependence for the first time.