k-Coloring is Faster than Computing the Chromatic Number

View PDF HTML (experimental) Abstract:We prove that $k$-coloring on $n$-vertex graphs has a randomized algorithm running in time $(2-\varepsilon_k)^n$, where $\varepsilon_k>0$ for every fixed $k$. Previously, only the cases $k\leq 6$ were known to have faster solutions than the general $O^\star\bigl(2^n\bigr)$ time algorithm of [Björklund, Husfeldt, Koivisto, SICOMP 2009] that computes the chromatic number. We resolve this long-standing open problem by generalizing and combining tools from the $(k+2)$-coloring to $k$-list-coloring reduction of [Zamir, ICALP 2021] and the hypergraph-containers based approach in [Zamir, STOC 2023]. Together with new algorithms for list-coloring instances mixing long and short color lists, this yields an iterable reduction from $(k+1)$-list-coloring to $k$-list-coloring over fixed palettes. Subjects: Data Structures and Algorithms (cs.DS) Cite as: arXiv:2607.25973 [cs.DS] (or arXiv:2607.25973v1 [cs.DS] for this version) https://doi.org/10.48550/arXiv.2607.25973 arXiv-issued DOI via DataCite (pending registration) Submission history From: Or Zamir [view email] [v1] Tue, 28 Jul 2026 16:53:58 UTC (47 KB)