{"id":"arxiv/2606.27159","url":"https://arxiv.org/abs/2606.27159","tags":["math.CO","cs.DM"],"score":0,"title":"Counting equitable $k$-colorings in graphs of bounded clique-width","domain":"math.CO","source":"arxiv","authors":["Holger Dell","Thore Husfeldt","Amir Nikabadi"],"reviews":0,"subject":"math.CO","summary":"For a graph $G$, a proper $k$-coloring of $G$ is \\emph{equitable} if the sizes of any two color classes differ by at most one. The \\textsc{Equitable $k$-Coloring} problem asks, for a given graph $G$ and integer $k$, whether $G$ admits an equitable $k$-coloring. Bodlaender and Fomin showed that it is polynomial-time solvable on graphs of bounded treewidth, while it remains $\\NP$-hard on cographs, and thus on graphs of constant clique-width. Fellows et al. showed that the problem becomes $\\mathsf{W[1]}$-hard when parameterized by tree-width (and hence clique-width) plus the number of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-25","reactions":{}}