Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Finer Tight Bounds for Coloring on Clique-Width   We revisit the complexity of the classical $k$-Coloring problem parameterized
by clique-width. This is a very well-studied problem that becomes highly
intractable when the number of colors $k$ is large. However, much less is known
on its complexity for small, concrete values of $k$. In this paper, we
completely determine the complexity of $k$-Coloring parameterized by
clique-width for any fixed $k$, under the SETH. Specifically, we show that for
all $k\ge 3,\epsilon>0$, $k$-Coloring cannot be solved in time
$O^*((2^k-2-\epsilon)^{cw})$, and give an algorithm running in time
$O^*((2^k-2)^{cw})$. Thus, if the SETH is true, $2^k-2$ is the "correct" base
of the exponent for every $k$.
  Along the way, we also consider the complexity of $k$-Coloring parameterized
by the related parameter modular treewidth ($mtw$). In this case we show that
the "correct" running time, under the SETH, is $O^*({k\choose \lfloor
k/2\rfloor}^{mtw})$. If we base our results on a weaker assumption (the ETH),
they imply that $k$-Coloring cannot be solved in time $n^{o(cw)}$, even on
instances with $O(\log n)$ colors.

32
The categories of this paper are: atom-ph
2
The categories of this paper are: math
3
The categories of this paper are: physics
18
The categories of this paper are: econ
22
The categories of this paper are: chao-dyn
12
The categories of this paper are: nucl-th
27
The categories of this paper are: comp-gas
29
The categories of this paper are: funct-an
17
The categories of this paper are: q-fin
24
The categories of this paper are: dg-ga
36
The categories of this paper are: cmp-lg
28
The categories of this paper are: alg-geom
6
The categories of this paper are: astro-ph
16
The categories of this paper are: stat
35
The categories of this paper are: mtrl-th
26
The categories of this paper are: bayes-an