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. 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.