Finer Tight Bounds for Coloring on Clique-Width

We revisit the complexity of the classical k-Coloring problem parameterized by clique-width. This is a very well-studied problem that becomes highly intractable when the number of colors k is large. However, much less is known on its complexity for small, concrete values of k. In this paper, we completely determine, under the Strong Exponential Time Hypothesis (SETH), for any fixed constant k, the complexity of k-Coloring parameterized by clique-width. Specifically, we show that for all k≥ 3,ε>0, k-Coloring cannot be solved in time O^*((2ᵏ-2-ε)^cw), and give an algorithm running in time O^*((2ᵏ-2)^cw). Thus, if the SETH is true, 2ᵏ-2 is the “correct” base of the exponent for every fixed k. Along the way, we also consider the complexity of k-Coloring parameterized by the related parameter modular treewidth (mtw). In this case we show that the “correct” running time under the SETH is O^*(k k/2^mtw). If we base our results on a weaker assumption (the ETH), they imply that k-Coloring cannot be solved in time n^o(cw), even on instances with O(log n) colors.