{"id":"arxiv/2610.01071","url":"https://arxiv.org/abs/2610.01071","tags":["cs.DS","cs.CC","cs.DM","math.CO"],"score":0,"title":"Coloring 3-colorable graphs with $O(n^{4/23})$ colors via a Gaussian-cover recursion","domain":"cs.DS","source":"arxiv","authors":["Emile Anand"],"reviews":0,"subject":"cs.DS","summary":"We give a randomized polynomial-time algorithm that colors any promised $3$-colorable graph on $n$ vertices with $\\smash{O(n^{4/23}) = O(n^{0.17391\\ldots})}$ 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})/18+ε})=O(n^{0.17506\\dots + ε})$ colors for every fixed $\\smash{ε>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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}