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 the complexity of k-Coloring parameterized by clique-width for any fixed k, under the SETH. Specifically, we show that for all k≥ 3,ε>0, k-Coloring cannot be solved in time O^*((2k-2-ε)cw), and give an algorithm running in time O^*((2k-2)cw). Thus, if the SETH is true, 2k-2 is the "correct" base of the exponent for every 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^*(kchoose lfloor k/2rfloormtw). If we base our results on a weaker assumption (the ETH), they imply that k-Coloring cannot be solved in time no(cw), even on instances with O(log n) colors.