Fixed-$k$ graph coloring below $2^n$ time

The question, posed by Zamir, asks whether fixed-$k$ coloring can beat the general $2^n$ bound for every fixed $k>6$. It is now answered affirmatively, in fact for every fixed $k$.

Known results

• Zamir had established sub-$2^n$ algorithms for $k\leq 6$, extending earlier results for $k\leq 4$.

July 2026 breakthrough

Two independent arXiv manuscripts prove that, for every fixed $k$, some $\varepsilon_k>0$ gives a randomized one-sided-error algorithm running in $O((2-\varepsilon_k)^n)$ time. Both obtain the result through stronger fixed-palette list-coloring theorems; one explicitly identifies Zamir's proof as concurrent and independent.

Current status (as of July 2026): Fixed-$k$ graph coloring is resolved for every fixed $k>6$ by unconditional randomized algorithms running in $O((2-\varepsilon_k)^n)$ time; no deterministic improvement is established here.