Skip to content
Preprint

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

Oct 2026 · 0 citations · 26 references
Computer Science Mathematics

TL;DR

A randomized polynomial-time algorithm that colors any promised $3$-colorable graph on $n$ vertices with O(n^{0.17506\dots + \epsilon}) colors is given, 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.

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+\epsilon})=O(n^{0.17506\dots + \epsilon})$ colors for every fixed $\smash{\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\geq 2$ centered linear forms with coefficient norms at most $r$, mean $\mu$, and variance $v$, we prove $v\leq r^2-\mu^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.

View source

Similar papers

Preprint Oct 2026

An $O(n^{0.1537})$-Coloring Algorithm for 3-Colorable Graphs

We present a polynomial-time randomized algorithm that colors every $n$-vertex $3$-colorable graph with $O(n^{0.1537})$ colors. This improves upon the previous bound of $O(n^{0.1954})$ colors by Bansal, Huang, and Lee (SODA'27). To achieve this result, we introduce a new algorithmic framework for finding a large indepe...

Kaisei Deguchi, K. Kawarabayashi, Hirotaka Yoneda et al. · 0 citations
Sep 2026

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

We give a randomized polynomial-time algorithm that, for every fixed $\varepsilon>0$, colors every $3$-colorable $n$-vertex graph using $O\bigl(n^{(13-\sqrt{97})/18+\varepsilon}\bigr) \approx O\bigl(n^{0.17506+\varepsilon}\bigr)$ colors, improving upon the previous best bound of $O(n^{0.19539})$ from Bansal, Huang, and...

Ijay Narang, Yu-Kai Tang · 1 citation · ⚡1
Preprint Oct 2026

Hardness of Coloring $2$-Colorable $3$-Uniform Hypergraphs with $\log^{\Omega(1)} n$ Colors

We show that it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices using $O((\log n)^{1/8})$ colors. This exponentially improves the result of Dinur, Regev, and Smyth [Combinatorica'2005], which showed it is quasi-NP-hard to color a $2$-colorable $3$-uniform hypergraph on $n$ vertices usin...

Amey Bhangale, KM KrishnaPriya, Simon Rubin-Toles · 0 citations
Preprint Oct 2026

Dynamic $(\Delta+1)$ Vertex Coloring with Adaptive Adversaries: Entropy Compression to the Rescue

We present a randomized algorithm for maintaining a $(\Delta+1)$ vertex coloring of a fully dynamic graph against an adaptive adversary with $\tilde{O}(\sqrt{n})$ amortized update time. Our algorithm improves upon the recent randomized algorithms of Behnezhad, Rajaraman, and Wasim (SODA 2025) with $\tilde{O}(n^{8/9})$...

Sepehr Assadi, Helia Yazdanyar · 1 citation
Preprint Oct 2026

The chromatic number of a random graph with $o(n^{3/2})$ edges

Let $G(n,m)$ be the Erdos-Renyi random graph with $n$ vertices and $m$ edges and let $\delta>0$. Alon and Krivelevich [Combinatorica 1997] proved that for any sequence $m\leq n^{3/2-\delta}$ there \emph{exists} an integer sequence $q=q(n)$ such that the chromatic number of $G(n,m)$ equals either $q$ or $q+1$ with proba...

Amin Coja-Oghlan, Mikhail Isaev, Mih-Yun Kang et al. · 1 citation
Preprint Nov 2026

Deterministic $n^{O(\log n)}$ Graph Isomorphism Algorithm via Inherited Decompositions

We give a deterministic $n^{O(\log d)}$-time algorithm for isomorphism of graphs with $n$ vertices and maximum degree $d$. Since $d<n$, this is an $n^{O(\log n)}$-time algorithm for graph isomorphism. To our knowledge, this is the first proof of such a worst-case bound for general graphs. It improves the explicit cubic...

M. Hajiaghayi, Mahdi JafariRaviz · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.