Breaking the $2^n$ barrier for graph $k$-coloring

Abstract

We show that for all $k$, there exists ${\epsilon }_k>0$ such that graph $k$-coloring can be solved by a randomized algorithm with one-sided error in time $O((2-{\epsilon }_k{)}^n)$. Prior to this work and independent concurrent work of Zamir [arXiv, 2026], exponential improvements over the $2^n\cdot \mathrm{poly}(n)$-time algorithm of Björklund, Husfeldt, and Koivisto [SIAM Journal on Computing, 2009] were only known for $k\le 6$.