2026-08-21T18:34:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27408 2026-08-21T14:42:38Z ddc:004 open_access

Counting Equitable k-Colorings in Graphs of Bounded Clique-Width Dell, Holger Husfeldt, Thore Nikabadi, Amir Equitable coloring Clique-width P_t-free graphs For a graph G, a proper k-coloring of G is equitable if the sizes of any two color classes differ by at most one. The Equitable k-Coloring problem asks, for a given graph G and integer k, whether G admits an equitable k-coloring. Bodlaender and Fomin (Theoretical Computer Science 2005) 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. (Information and Computation 2011) showed that the problem becomes W[1]-hard when parameterized by tree-width (and hence clique-width) plus the number of colors k. We first show that, there exists an algorithm, given an integer k ≥ 1 and an n-vertex graph G together with a w-expression whose underlying unlabelled graph is G, computes the number of equitable k-colorings of G in time 2^O(k⋅w) ⋅ n^O(k). In particular, we show that for every fixed k, counting equitable k-colorings is polynomial-time solvable on graph classes of bounded clique-width, given a clique-width expression. We then show that, under SETH, the dependence on clique-width in this algorithm is essentially optimal. As a consequence, our results provide a fairly tight picture of the complexity of Equitable k-Coloring with respect to the combined parameter k+clique-width in the following sense: For variable k, the problem is W[1]-hard, however for every fixed integer k, it is polynomial-time solvable on graphs of bounded clique-width given a clique-width expression, and this remains true even for the counting version. Second, we refine our clique-width algorithm for the linear setting. We show that there exists an algorithm, given an integer k ≥ 1 and an n-vertex graph G together with a linear w-expression constructing G, computes the number of equitable k-colorings of G in time max{1,2^k-2}^w ⋅ n^{k+O(1)}. Thus, for bounded linear clique-width, we obtain a significantly sharper dependence on the width parameter than in the general clique-width case. Third, we consider a different structural restriction, namely the class of P_t-free graphs. A graph is called P_t-free if it does not contain the path on t vertices as an induced subgraph. This is a different setting from bounded clique-width; in particular, already P₅-free graphs have unbounded clique-width. Nevertheless, we show that for every P_t-free graph G, the number of equitable list 3-colorings of G can be computed in subexponential time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Holger Dell and Thore Husfeldt and Amir Nikabadi 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.27 urn:nbn:de:0030-drops-274085 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.27 eng https://creativecommons.org/licenses/by/4.0/legalcode