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 O~*((q - ε)~k), for any ε > 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 unless ETH fails, there is no universal constant θ such that q-COLORING parameterized by vertex cover can be solved in time O~*(θ~k) for all fixed q. We prove that there are O~*((q - ε)~k) time algorithms where k is the vertex deletion distance to several graph classes F for which q-COLORING is known to be solvable in polynomial time, including all graph classes whose (q + 1)-colorable members have bounded treedepth. In contrast, we prove that if F is the class of paths - some of the simplest graphs of unbounded treedepth - then no such algorithm can exist unless SETH fails.
展开▼
