k-Coloring is Faster than Computing the Chromatic Number

We prove that k-coloring on n-vertex graphs has a randomized algorithm running in time (2-eps_k)^n, where eps_k>0 for every fixed k. 

Previously, only the cases k<7 were known to have faster solutions than the general 2^n time algorithm of [Bjorklund, Husfeldt, Koivisto, SICOMP 2009] that computes the chromatic number. In fact, our algorithm solves the more general problem of k-list-coloring, even when the overall color palette is of unbounded size.

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 arbitrary palettes.