Breaking the $2^n$ barrier for 5-coloring and 6-coloring

Or Zamir

The coloring problem (i.e., computing the chromatic number of a graph) can be solved in $O^{\ast }(2^n)$ time, as shown by Björklund, Husfeldt and Koivisto in 2009. For $k=3,4$, better a…