k-Coloring Is Now Faster Than Computing the Chromatic Number

k-Coloring is Faster than Computing the Chromatic Number

A new paper by Or Zamir proves that k-coloring on n-vertex graphs can be solved in randomized time (2−ε_k)^n for every fixed k, where ε_k > 0. Previously, only k ≤ 6 had faster algorithms than the general O*(2^n) chromatic number algorithm. The result resolves a long-standing open problem by generalizing and combining tools from a (k+2)-coloring to k-list-coloring reduction and hypergraph containers, plus new algorithms for list-coloring instances with mixed color list lengths.