Counting equitable $k$-colorings in graphs of bounded clique-width
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.27159
curl -X POST /api/v1/records/arxiv/2606.27159/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.27159/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'