בניין מדעי המחשב

Or Zamir

Tel Aviv University

ירצה על

Will lecture on

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

The problem of k-coloring a graph, or determining the chromatic number of a graph (i.e., finding the smallest k for which the graph is k-colorable) is another one of the most classic and well studied NP-Complete problems.
Following a long line of work, Bjorklund, Husfeldt and Koivisto showed in 2009 that the chromatic number of a graph can be computed in O*(2^n) time, where n is the number of vertices in the graph.
Deciding whether a graph is 3-colorable can be done in O(1.33^n) time (Beigel and Eppstein, 2005) and deciding whether it is 4-colorable can be done in O(1.73^n) time (Fomin, Gaspers and Saurabh, 2007).
Surprisingly, for k>4 no improvements over the general O^*(2^n) were known.

In the discussed work, we show that both 5-coloring and 6-coloring can also be solved in O((2-eps)^n) time for some eps>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 D,a>0, the chromatic number of graphs with at least a*n vertices of degree at most D can be computed in O((2-eps)^n) time, for some eps = eps_{D,a} > 0.
This statement generalizes previous results for bounded-degree graphs (Bjorklund, Husfeldt, Kaski, and Koivisto, 2010) and graphs with bounded average degree (Golovnev, Kulikov and Mihajilin, 2016).