Fine-grained parameterized complexity analysis of graph coloring problems

The q-COLORING problem asks whether the vertices of a graph can be properly colored with q colors. In this paper we perform a fine-grained analysis of the complexity of q-COLORING with respect to a hierarchy of structural parameters. We show that unless the Exponential Time Hypothesis fails, there is no constant θ such that q-COLORING parameterized by the size k of a vertex cover can be solved in O ^∗(θ ^k) time 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 for which q-COLORING is known to be solvable in polynomial time, including all graph classes F 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 the Strong Exponential Time Hypothesis fails.