"Breaking the 2^n barrier for 5-coloring and 6-coloring"
Or Zamir (IAS)
Monday, April 5th 2021, 2-3pm
Abstract:
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.33^n) time (Beigel and Eppstein, 2005) and 4-coloring can be solved in O(1.73^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.
As a crucial step, we obtain an exponential improvement for computing the chromatic number of a very large family of graphs. In particular, for any constants Δ,α>0, the chromatic number of graphs with at least α⋅n vertices of degree at most Δ can be computed in O((2−ε)^n) time, for some ε=ε_{Δ,α}>0.