论文标题
打破$ 2^n $壁垒的5色和6色
Breaking the $2^n$ barrier for 5-coloring and 6-coloring
论文作者
论文摘要
颜色问题（即计算图的色度数）可以以$ o^*（2^n）$时间解决，如Björklund，Husfeldt和Koivisto在2009年所示。对于$ k = 3,4 $，以$ k $ - 颜色的问题而闻名。 $ 3 $ - 颜色可以用$ O（1.33^n）$ TIME（Beigel和Eppstein，2005年）和$ 4 $ - 颜色可以用$ O（1.73^n）$ TIME（FOMIN，GASPERS和SAURABH，2007）解决。令人惊讶的是，对于$ k> 4 $，对一般$ o^*（2^n）$没有改进。我们表明，$ 5 $ - 颜色和$ 6 $ - 颜色也可以在$ o \ left中解决（\ left（2- \ varepsilon \ right）^n \ right）$ \ varepsilon> 0 $。作为关键步骤，我们获得了计算非常大的图表的色数的指数改进。特别是，对于任何常数$δ，α> 0 $，最多可以在$ o \ left中计算至少$α\ cdot n $学位的图形数字（\ left（2- \ varepsilon \ right）^n \ right）$ \ varepsilon = varepsiLON = $ $ a。该声明概括了有界度图的先前结果（Björklund，Husfeldt，Kaski和Koivisto，2010年），并具有有界平均程度的图（Golovnev，Kulikov和Mihajilin，2016年）。我们将上述语句概括为列出着色，即使对于案例有限度图，也没有以前的改进。
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\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 $Δ,α>0$, the chromatic number of graphs with at least $α\cdot n$ vertices of degree at most $Δ$ can be computed in $O\left(\left(2-\varepsilon\right)^n\right)$ time, for some $\varepsilon = \varepsilon_{Δ,α} > 0$. This statement generalizes previous results for bounded-degree graphs (Björklund, 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.
