Coloring 3-colorable graphs with O(n4/23) colors via a Gaussian-cover recursion
Abstract
We give a randomized polynomial-time algorithm that colors any promised $3$-colorable graph on n vertices with smashO(n4/23) = O(n0.17391…) colors, improving on the recent bounds of O(n0.19539) by Bansal, Huang, and Lee and Narang and Tang who obtained O(n(13−√(97))/18+ε)=O(n0.17506… + ε) 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 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≥ 2 centered linear forms with coefficient norms at most r, mean μ, and variance v, we prove v≤ r2−μ2/(2log 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.
Related
BibTeX
@misc{anand2026coloring,
title = {{Coloring 3-colorable graphs with $O(n^4/23)$ colors via a Gaussian-cover recursion}},
author = {Emile Anand},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01071},
eprint = {2610.01071},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01071},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Coloring 3-colorable graphs with O(n^4/23) colors via a Gaussian-cover recursion
AU - Emile Anand
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01071
UR - https://arxiv.org/abs/2610.01071
AB - We give a randomized polynomial-time algorithm that colors any promised $3$-colorable graph on n vertices with smashO(n^4/23) = O(n^0.17391…) 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−√(97))/18+ε)=O(n^0.17506… + ε) 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 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≥ 2 centered linear forms with coefficient norms at most r, mean μ, and variance v, we prove v≤ r^2−μ^2/(2log 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.
ER -