Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Breaking the $2^n$ barrier for 5-coloring and 6-coloring   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 =
\varepsilon_{\Delta,\alpha} > 0$. 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.

9
The categories of this paper are: nlin
18
The categories of this paper are: econ
30
The categories of this paper are: q-alg
21
The categories of this paper are: adap-org
0
The categories of this paper are: hep-ph
23
The categories of this paper are: solv-int
35
The categories of this paper are: mtrl-th
37
The categories of this paper are: supr-con
4
The categories of this paper are: cond-mat
2
The categories of this paper are: math
33
The categories of this paper are: plasm-ph
31
The categories of this paper are: ao-sci
22
The categories of this paper are: chao-dyn
19
The categories of this paper are: eess
7
The categories of this paper are: hep-th
27
The categories of this paper are: comp-gas