In a colouring of a graph, a vertex is b-chromatic if it is adjacent to a vertex of every other colour. We consider four well-studied colouring problems: b-Chromatic Number, Tight b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number, which fit into a framework based on whether every colour class has (i) at least one b-chromatic vertex, (ii) exactly one b-chromatic vertex, or (iii) all of its vertices being b-chromatic. By combining known and new results, we fully classify the computational complexity of b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number in H-free graphs. For Tight b-Chromatic Number in H-free graphs, we develop a general technique to determine new graphs H, for which the problem is polynomial-time solvable, and we also determine new graphs H, for which the problem is still NP-complete. We show, for the first time, the existence of a graph H such that in H-free graphs, b-Chromatic Number is NP-hard, while Tight b-Chromatic Number is polynomial-time solvable.

We consider Colouring on graphs that are $H$-subgraph-free for some fixed graph $H$, which are graphs that do not contain $H$ as a subgraph. To classify the complexity of Colouring on $H$-subgraph-free graphs for connected $H$, it remains to consider when $H$ is a tree of maximum degree $4$ with exactly one vertex of degree $4$, or a tree of maximum degree $3$ with at least two vertices of degree $3$. We let $H$ be a so-called subdivided ``H''-graph, which is either a subdivided $\mathbb{H}_0$: a tree of maximum degree $4$ that is a star, or a subdivided $\mathbb{H}_1$: a tree of maximum degree $3$ with exactly two vertices of degree $3$. We develop new decomposition theorems resulting in polynomial-time algorithms, and in combination with known results, fully classify all cases $\mathbb{H}_0$ and $\mathbb{H}_1$. To illustrate the wider applicability of our techniques, we also employ them to obtain similar new polynomial-time results for two other classic graph problems: Stable Cut and, in part, Feedback Vertex Set.

The Matching Cut problem is to decide if the vertex set of a connected graph can be partitioned into two non-empty sets B and R such that the edges between B and R form a matching, that is, every vertex in B has at most one neighbour in R, and vice versa. If for some integer d ≥ 1, we allow every vertex in B to have at most d neighbours in R, and vice versa, we obtain the more general problem d-Cut. It is known that d-Cut is NP-complete for every d ≥ 1. However, for claw-free graphs, it is only known that d-Cut is polynomial-time solvable for d = 1 and NP-complete for d ≥ 3. We resolve the missing case d = 2 by proving NP-completeness. This follows from our more general study, in which we also bound the maximum degree. That is, we prove that for every d ≥ 2, d-Cut, restricted to claw-free graphs of maximum degree p, is constant-time solvable if p ≤ 2d+1 and NP-complete if p ≥ 2d+3. Moreover, in the former case, we can find a d-cut in linear time. We also show how our positive results for claw-free graphs can be generalized to S_{1^t,𝓁}-free graphs where S_{1^t,𝓁} is the graph obtained from a star on t+2 vertices by subdividing one of its edges exactly 𝓁 times.

Abstract The (Perfect) Matching Cut problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a connected graph has a perfect matching that contains a matching cut. Both Matching Cut and Disconnected Perfect Matching are -complete for planar graphs of girth 5, whereas Perfect Matching Cut is known to be -complete even for subcubic bipartite graphs of arbitrarily large fixed girth. We prove that Matching Cut and Disconnected Perfect Matching are also -complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Our result for Matching Cut resolves a 20-year old open problem. We also show that the more general problem d -Cut, for every fixed $$d\ge 1$$ d ≥ 1 , is -complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Furthermore, we show that Matching Cut, Perfect Matching Cut and Disconnected Perfect Matching are -complete for H-free graphs whenever H contains a connected component with two vertices of degree at least 3. Afterwards, we update the state-of-the-art summaries for H-free graphs and compare them with each other, and with a known and full classification of the Maximum Matching Cut problem, which is to determine a largest matching cut of a graph G. Finally, by combining existing results, we obtain a complete complexity classification of Perfect Matching Cut for $$\mathcal{H}$$ H -subgraph-free graphs where $$\mathcal{H}$$ H is any finite set of graphs.

In the Matching Cut problem we ask whether a graph G has a matching cut, that is, a matching which is also an edge cut of G . We consider the variants Perfect Matching Cut and Disconnected Perfect Matching where we ask whether there exists a matching cut equal to, respectively, contained in a perfect matching. In addition, in the problem Maximum Matching Cut we ask for a matching cut with a maximum number of edges. The last problem we consider is d -Cut where we ask for an edge cut where each vertex is incident to at most d edges in the cut. We investigate the computational complexity of these problems on bipartite graphs of bounded radius and diameter. Our results extend known results for Matching Cut and Disconnected Perfect Matching . We give complexity dichotomies for d -Cut and Maximum Matching Cut and solve one of two open cases for Disconnected Perfect Matching . For Perfect Matching Cut we give the first hardness result for bipartite graphs of bounded radius and diameter and extend the known polynomial cases.

Abstract We consider the following problem: for a given graph G and two integers k and d, can we apply a fixed graph operation at most k times in order to reduce a given graph parameter $$\pi $$ π by at least d? We show that this problem is NP-hard when the parameter is the independence number and the graph operation is vertex deletion or edge contraction, even for fixed $$d=1$$ d = 1 and when restricted to chordal graphs. We give a polynomial time algorithm for bipartite graphs when the operation is edge contraction, the parameter is the independence number and d is fixed. Further, we complete the complexity dichotomy for H-free graphs when the parameter is the clique number and the operation is edge contraction by showing that this problem is NP-hard in $$(C_3+P_1)$$ ( C 3 + P 1 ) -free graphs even for fixed $$d=1$$ d = 1 . When the operation is edge deletion and the parameter is the chromatic number, we determine the computational complexity of the associated problem for cographs and complete multipartite graphs. Our results answer several open questions stated in Diner et al. (Theor Comput Sci 746:49–72, 2012, https://doi.org/10.1016/j.tcs.2018.06.023 ).

In this paper, we consider the following two problems: (i) Deletion Blocker ( α ) where we are given an undirected graph G = ( V , E ) and two integers k , d ≥ 1 and ask whether there exists a subset of vertices S ⊆ V with | S | ≤ k such that α ( G − S ) ≤ α ( G ) − d , that is the independence number of G decreases by at least d after having removed the vertices from S ; (ii) Transversal ( α ) where we are given an undirected graph G = ( V , E ) and two integers k , d ≥ 1 and ask whether there exists a subset of vertices S ⊆ V with | S | ≤ k such that for every maximum independent set I we have | I ∩ S | ≥ d . We show that both problems are polynomial-time solvable in the class of co-comparability graphs by reducing them to the well-known Vertex Cut problem. Our results generalise a result of Chang et al. (2001) and a recent result of Hoang et al. (2023).

Matching cut Perfect matching 𝐻-free graph Diameter Radius DichotomyThe (Perfect) Matching Cut problem is to decide if a graph 𝐺 has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of 𝐺.Both Matching Cut and Perfect Matching Cut are known to be NP-complete.A perfect matching cut is also a matching cut with maximum number of edges.To increase our understanding of the relationship between the two problems, we perform a complexity study for the Maximum Matching Cut problem, which is to determine a largest matching cut in a graph.Our results yield full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and 𝐻-free graphs.A disconnected perfect matching of a graph 𝐺 is a perfect matching that contains a matching cut of 𝐺.We also show how our new techniques can be used for finding a disconnected perfect matching with a largest matching cut for special graph classes.In this way we can prove that the decision problem Disconnected Perfect Matching is polynomial-time solvable for (𝑃 6 + 𝑠𝑃 2 )-free graphs for every 𝑠 ≥ 0, extending a known result for 𝑃 5 -free graphs (Bouquet and Picouleau, 2020).

International audience

The (Perfect) Matching Cut problem is to decide if a graph $G$ has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of $G$. Both Matching Cut and Perfect Matching Cut are known to be NP-complete. A perfect matching cut is also a matching cut with maximum number of edges. To increase our understanding of the relationship between the two problems, we perform a complexity study for the Maximum Matching Cut problem, which is to determine a largest matching cut in a graph. Our results yield full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and $H$-free graphs. A disconnected perfect matching of a graph $G$ is a perfect matching that contains a matching cut of $G$. We also show how our new techniques can be used for finding a disconnected perfect matching with a largest matching cut for special graph classes. In this way we can prove that the decision problem Disconnected Perfect Matching is polynomial-time solvable for $(P_6+sP_2)$-free graphs for every $s\geq 0$, extending a known result for $P_5$-free graphs (Bouquet and Picouleau, 2020).

Abstract The well-known -complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. We also prove new complexity results for two recently studied variants of Matching Cut, on H-free graphs. The first variant requires that the matching cut must be extendable to a perfect matching of the graph. The second variant requires the matching cut to be a perfect matching. In particular, we prove that there exists a small constant $$r>0$$ r > 0 such that the first variant is -complete for $$P_r$$ P r -free graphs. This addresses a question of Bouquet and Picouleau (The complexity of the Perfect Matching-Cut problem. CoRR, arXiv:2011.03318 , (2020)). For all three problems, we give state-of-the-art summaries of their computational complexity for H-free graphs.

Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that contains an edge-cut. We show that this problem is NP-complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five-regular graphs, for graphs of diameter three and for bipartite graphs of diameter four. We show that there exist polynomial time algorithms for the following classes of graphs: claw-free, $P_5$-free, diameter two, bipartite with diameter three and graphs with bounded tree-width.

For a connected graph G=(V,E), a matching M⊆E is a matching cut of G if G−M is disconnected. It is known that for an integer d, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most d if d≤2 and NP-complete if d≥3. We prove the same dichotomy for graphs of bounded radius. For a graph H, a graph is H-free if it does not contain H as an induced subgraph. As a consequence of our result, we can solve Matching Cut in polynomial time for P6-free graphs, extending a recent result of Feghali for P5-free graphs. We then extend our result to hold even for (sP3+P6)-free graphs for every s≥0 and initiate a complexity classification of Matching Cut for H-free graphs.