Title: Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems,
Abstract: The $q$-Coloring problem asks whether the vertices of a graph can be properly
colored with $q$ colors. Lokshtanov et al. [SODA 2011] showed that $q$-Coloring
on graphs with a feedback vertex set of size $k$ cannot be solved in time
$\mathcal{O}^*((q-\varepsilon)^k)$, for any $\varepsilon > 0$, unless the
Strong Exponential-Time Hypothesis (SETH) fails. In this paper we perform a
fine-grained analysis of the complexity of $q$-Coloring with respect to a
hierarchy of parameters. We show that even when parameterized by the vertex
cover number, $q$ must appear in the base of the exponent: Unless ETH fails,
there is no universal constant $\theta$ such that $q$-Coloring parameterized by
vertex cover can be solved in time $\mathcal{O}^*(\theta^k)$ for all fixed $q$.
We apply a method due to Jansen and Kratsch [Inform. & Comput. 2013] to prove
that there are $\mathcal{O}^*((q - \varepsilon)^k)$ time algorithms where $k$
is the vertex deletion distance to several graph classes $\mathcal{F}$ for
which $q$-Coloring is known to be solvable in polynomial time. We generalize
earlier ad-hoc results by showing that if $\mathcal{F}$ is a class of graphs
whose $(q+1)$-colorable members have bounded treedepth, then there exists some
$\varepsilon > 0$ such that $q$-Coloring can be solved in time
$\mathcal{O}^*((q-\varepsilon)^k)$ when parameterized by the size of a given
modulator to $\mathcal{F}$. In contrast, we prove that if $\mathcal{F}$ is the
class of paths - some of the simplest graphs of unbounded treedepth - then no
such algorithm can exist unless SETH fails.