2017/01/24 by Lars Jaffke, Jaffke, Lars, Bart M. P. Jansen +1 · 1 citation
Computer Science · #05C85 #68Q25 #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1701.06985
openalex publication_date 2017/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 θ such that q-Coloring parameterized by vertex cover can be solved in time O^*(θk) for all fixed q. We apply a method due to Jansen and Kratsch [Inform. & Comput. 2013] to 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. We generalize earlier ad-hoc results by showing that if F is a class of graphs whose (q+1)-colorable members have bounded treedepth, then there exists some ε > 0 such that q-Coloring can be solved in time O^*((q-ε)k) when parameterized by the size of a given modulator to F. 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.