2026/07/28 by Or Zamir · 1 voice
#cs.DS
We prove that k-coloring on n-vertex graphs has a randomized algorithm running in time (2-εk)n, where εk>0 for every fixed k. Previously, only the cases k≤ 6 were known to have faster solutions than the general O^⋆(2n) 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.