Improving coloring algorithms for three colorable graphs efficiently
Coloring 3-colorable graphs with $O(n^{4/23})$ colors via a Gaussian-cover recursion
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
Summary
Graph coloring is a way to assign colors to points in a network so that connected points have different colors. Some networks can be colored with just three colors, but finding such a coloring quickly is hard. The authors developed a new algorithm that produces a coloring using many fewer colors than previous methods, making it closer to the ideal three colors. They used advanced math tools involving Gaussian distributions and recursion to achieve this improvement.
What this means in practice
- •For graph algorithm developers: Develop more efficient heuristics for coloring problems in sparse networks by adapting the improved coloring bounds in 3-colorable graphs.
- •For optimization software engineers: Incorporate advanced semidefinite relaxation and Gaussian-based recursion techniques to improve combinatorial optimization solvers handling graph colorings.
A theory result. No direct application yet.
Authors
Emile Anand
Abstract
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 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\geq 2$ centered linear forms with coefficient norms at most $r$, mean $μ$, and variance $v$, we prove $v\leq r^2-μ^2/(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.