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.

The Upper Clique Transversal (UCT) problem asks for the size of the largest minimal set of vertices intersecting all the maximal cliques of the input graph. This problem was recently introduced by Milanič and Uno [WG 2023], who studied its complexity on several graph classes. They showed that the problem is NP-hard on chordal graphs, and gave polynomial-time algorithms for UCT on split and on proper interval graphs. They left open the complexity of UCT on interval graphs. In this work we settle this question by giving a polynomial-time algorithm for UCT on interval graphs. We show that even on the more general class of rooted directed path graphs, which can be understood as a "tree-like version" of interval graphs, the problem remains polynomial-time solvable. On the negative side, we observe as consequences of the NP-hardness proof for chordal graphs due to Milanič and Uno that the problem is NP-hard on graphs of path-independence number two (interval graphs have path-independence number one) and on well-partitioned chordal graphs which lie between split and chordal graphs.

We show that, for every fixed positive integers $r$ and $k$, \textsc{Max-Weight List $r$-Colorable Induced Subgraph} admits a polynomial-time algorithm on $kP_3$-free graphs. This problem is a common generalization of \textsc{Max-Weight Independent Set}, \textsc{Odd Cycle Transversal} and \textsc{List $r$-Coloring}, among others. Our result has several consequences. First, it implies that, for every fixed $r \geq 5$, assuming $\mathsf{P}\neq \mathsf{NP}$, \textsc{Max-Weight List $r$-Colorable Induced Subgraph} is polynomial-time solvable on $H$-free graphs if and only if $H$ is an induced subgraph of either $kP_3$ or $P_5+kP_1$, for some $k \geq 1$. Second, it makes considerable progress toward a complexity dichotomy for \textsc{Odd Cycle Transversal} on $H$-free graphs, allowing to answer a question of Agrawal, Lima, Lokshtanov, Rz{ą}{ż}ewski, Saurabh, and Sharma [TALG 2024]. Third, it gives a short and self-contained proof of the known result of Chudnovsky, Hajebi, and Spirkl [Combinatorica 2024] that \textsc{List $r$-Coloring} on $kP_3$-free graphs is polynomial-time solvable for every fixed $r$ and $k$. We also consider two natural distance-$d$ generalizations of \textsc{Max-Weight Independent Set} and \textsc{List $r$-Coloring} and provide polynomial-time algorithms on $kP_3$-free graphs for every fixed integers $r$, $k$, and $d \geq 6$.

Subgraph detection has recently been one of the most studied problems in the CONGEST model of distributed computing. In this work, we study the distributed complexity of problems closely related to subgraph detection, mainly focusing on induced subgraph detection. The main line of this work presents lower bounds and parameterized algorithms w.r.t structural parameters of the input graph: - On general graphs, we give unconditional lower bounds for induced detection of cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions from centralized parameterized complexity, we prove lower bounds in CONGEST for detecting patterns with a 4-clique, and for induced path detection conditional on the hardness of triangle detection in the congested clique. - On graphs of bounded degeneracy, we show that induced paths can be detected fast in CONGEST using techniques from parameterized algorithms, while detecting cycles and patterns of treewidth 2 is hard. - On graphs of bounded vertex cover number, we show that induced subgraph detection is easy in CONGEST for any pattern graph. More specifically, we adapt a centralized parameterized algorithm for a more general maximum common induced subgraph detection problem to the distributed setting. In addition to these induced subgraph detection results, we study various related problems in the CONGEST and congested clique models, including for multicolored versions of subgraph-detection-like problems.