Coloring 3-colorable graphs with $O(n^{4\mathrm{/}23})$ colors via a Gaussian-cover recursion

We give a randomized polynomial-time algorithm that colors any promised $3$-colorable graph on $n$ vertices with $O(n^{4\mathrm{/}23})=O(n^{0.17391\dots })$ colors, improving on the recent bounds of $O(n^{0.19539})$ by Bansal, Huang, and Lee and Narang and Tang who obtained $O(n^{(13-\sqrt{97})\mathrm{/}18+\epsilon })=O(n^{0.17506\cdots +\epsilon })$ colors for every fixed $\epsilon >0$. To prove our result, we start from a fixed-level semidefinite relaxation, where we use a finite-depth recursion on Gaussian covers. Fixing a root vertex, we group vertices by correlation with the root vector. Here, each step extends a cover of directions by one edge and transfers it to a successor group. Our key analytic ingredient is a variance bound for Gaussian maxima: for a maximum of $m\ge 2$ centered linear forms with coefficient norms at most $r$, mean $\mu$, and variance $v$, we prove $v\le r^2-{\mu }^2\mathrm{/}(2\log m)$ using Chen’s Gaussian convexity theorem. Together with a variance-scale lower-tail estimate, this controls the threshold loss at each extension, which shows that root-conditioned vector colorings can either extract a large independent set from a group or bound its size, forcing a contradiction after constantly many steps. The resulting sparse-case guarantee combines with the dense progress bound of Kawarabayashi, Thorup, and Yoneda, and the recursion’s numerical inequalities are verified via rational interval arithmetic.