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.
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
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...
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
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})$...
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
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.