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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-25 Page: https://delphi.science/r/arxiv/2606.27159 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…