Breaking the $2^n$ barrier for graph $k$-coloring
2026-07-29 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors show that for any number of colors k, there is a faster randomized algorithm to solve the graph k-coloring problem than the previously best-known method. Their algorithm runs in time proportional to (2 minus some small number)^n, improving over the old 2^n time bound. Before this work and a similar result by Zamir, such improvements were only known for k up to 6. This means they extended the faster coloring methods to all values of k.
graph k-coloringrandomized algorithmone-sided errorexponential timealgorithmic complexityBjorklund-Husfeldt-Koivisto algorithmcombinatorial optimizationtime complexitypolynomial factor
Authors
Kevin Pratt
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$.