arXiv:2607.27159cs.DS
Breaking the $2^n$ barrier for graph $k$-coloring
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
We show that for all $k$, there exists $\varepsilon_k > 0$ such that graph $k$-coloring can be solved by a randomized algorithm with one-sided error in time $O((2-\varepsilon_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$.
Also see my concurrent result: https://arxiv.org/abs/2607.27159. Quantitatively, mine is slightly better :) my \eps_k is something like 1/2^2^2^k, Zamir gets a tower of height O(k).
in_betweenView on HNParent context