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-\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.
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.
Summary
A new randomized algorithm enables faster $k$-coloring for $n$-vertex graphs, achieving a runtime of $(2-\varepsilon_k)^n$ for any fixed $k$. This advancement surpasses previous methods, which were limited to $k \leq 6$, and addresses a significant open problem in computational graph theory.
Comments (13 of ) ⌛