Breaking the 2^n barrier for 5-coloring and 6-coloring
share
The coloring problem (i.e., computing the chromatic number of a graph) can be solved in O^*(2^n) time, as shown by Björklund, Husfeldt and Koivisto in 2009. For k=3,4, better algorithms are known for the k-coloring problem. 3-coloring can be solved in O(1.4^n) time (Beigel and Eppstein, 2005) and 4-coloring can be solved in O(1.8^n) time (Fomin, Gaspers and Saurabh, 2007). Surprisingly, for k>4 no improvements over the general O^*(2^n) are known. We show that both 5-coloring and 6-coloring can also be solved in O((2-ε)^n) time for some ε>0. Moreover, we obtain an exponential improvement for k-coloring for any constant k for a very large family of graphs. In particular, for any constants k,Δ,α>0, k-coloring for graphs with at least α· n vertices of degree at most Δ can be solved in O((2-ε)^n) time, for some ε = ε_k,Δ,α > 0. As a consequence, for any constant k we can solve k-coloring exponentially faster than O^*(2^n) for sparse graphs.
READ FULL TEXT