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 theta such that q-COLORING parameterized by the size k of a vertex cover can be solved in O*(theta k) time for all fixed q. We prove that there are O*((q - epsilon)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.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).