# Finer Tight Bounds for Coloring on Clique-Width

arXiv: https://arxiv.org/abs/1804.07975 · HTML: https://mlsanity.com/paper/1804.07975/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2018.

## Built on by (most cited first, 1 of 1)

- [Monte Carlo Graph Coloring](https://mlsanity.com/paper/2504.03277/) (2025)

## Abstract (arXiv)

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.