k-Coloring is Faster than Computing the Chromatic Number

Abstract

We prove that $k$-coloring on $n$-vertex graphs has a randomized algorithm running in time $(2-{\epsilon }_k{)}^n$, where ${\epsilon }_k>0$ for every fixed $k$. Previously, only the cases $k\le 6$ were known to have faster solutions than the general $O^{\star }\left(2^n\right)$ 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.