The coloring problem (i.e., computing the chromatic number of a graph) can be solved in O^*(2^n) time, as shown by Bj\"orklund, 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\left(\left(2-\varepsilon\right)^n\right) time for some \varepsilon>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, \Delta,\alpha>0, k-coloring for graphs with at least \alpha\cdot n vertices of degree at most \Delta can be solved in O\left(\left(2-\varepsilon\right)^n\right) time, for some \varepsilon = k, \Delta,\alpha As a consequence, for any constant k we can solve k-coloring exponentially faster than O^*(2^n) for sparse graphs.
The coloring problem (i.e., computing the chromatic number of a graph) can be solved in O^*(2^n) time, as shown by Bj\"orklund, 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\left(\left(2-\varepsilon\right)^n\right) time for some \varepsilon>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 \Delta,\alpha>0, the chromatic number of graphs with at least \alpha\cdot n vertices of degree at most \Delta can be computed in O\left(\left(2-\varepsilon\right)^n\right) time, for some \varepsilon = This statement generalizes previous results for bounded-degree graphs (Bj\"orklund, Husfeldt, Kaski, and Koivisto, 2010) and graphs with bounded average degree (Golovnev, Kulikov and Mihajilin, 2016). We generalize the aforementioned statement to List Coloring, for which no previous improvements are known even for the case bounded-degree graphs.
R
1.4
1.33
R
1.8
1.73
R
Moreover
As a crucial step
R
k-coloring for any constant k for
computing the chromatic number of
D
k,
R
k-coloring for
the chromatic number of
R
solved
computed
D
k, \Delta,\alpha
R
As a consequence, for any constant k we can solve k-coloring exponentially faster than O^*(2^n) for sparse
This statement generalizes previous results for bounded-degree graphs (Bj\"orklund, Husfeldt, Kaski, and Koivisto, 2010) and graphs with bounded average degree (Golovnev, Kulikov and Mihajilin, 2016). We generalize the aforementioned statement to List Coloring, for which no previous improvements are known even for the case bounded-degree