Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian Certificates

Abstract

We give a randomized polynomial-time algorithm that, for every fixed $\epsilon >0$, colors every $3$-colorable $n$-vertex graph using $O\left(n^{(13-\sqrt{97})/18+\epsilon }\right)\approx O\left(n^{0.17506+\epsilon }\right)$ colors, improving upon the previous best bound of $O(n^{0.19539})$ from Bansal, Huang, and Lee. Our improvement comes from analyzing higher-level neighborhoods through a recursive description of failure in Gaussian SDP rounding. If the rounding returns too small an independent set, it produces local Gaussian certificates at every vertex of a nonempty induced subgraph. We propagate these certificates along walks to higher-level neighborhoods by defining a recursive certificate structure and proving a strengthened cover-composition lemma, which refines the one of Arora, Chlamt{á}{č}, and Charikar. We then construct a bounded potential function that increases by a fixed positive amount at every propagation step, yielding a contradiction. Consequently, the rounding must produce a sufficiently large independent set.