Breaking the barrier for graph -coloring
arXiv:2607.27159
summary
The paper presents a randomized one‑sided error algorithm that solves graph k‑coloring in O((2‑ε_k)^n) time for any k, thus breaking the long‑standing 2^n time barrier.
Abstract
We show that for all , there exists such that graph -coloring can be solved by a randomized algorithm with one-sided error in time . Prior to this work and independent concurrent work of Zamir [arXiv, 2026], exponential improvements over the -time algorithm of Björklund, Husfeldt, and Koivisto [SIAM Journal on Computing, 2009] were only known for .
Topics & keywords
#graph coloring#exact exponential algorithms#randomized algorithms#algorithmic complexity#combinatorial optimizationgraph k-coloringrandomized algorithmone-sided error(2-ε)^n runtimeexponential time improvement