This paper continues the study of a new variant of graph coloring with a connectivity constraint recently introduced by Hsieh et al. (2024). A path in a vertex-colored graph is called conflict-free if there is a color that appears exactly once on its vertices. A connected graph is said to be strongly conflict-free vertex-connection k -colorable if it admits a (proper) vertex k -coloring such that any two distinct vertices are connected by a conflict-free shortest path. Among others, we show that deciding, for a given graph G and an integer k , whether G is strongly conflict-free vertex-connection k -colorable is fixed-parameter tractable when parameterized by the vertex cover number. But under the standard complexity-theoretic assumption NP ⊈ coNP/poly , deciding, for a given graph G , whether G is strongly conflict-free vertex-connection 3-colorable does not admit a polynomial kernel, even for bipartite graphs. This kernel lower bound is in stark contrast to the ordinal k - coloring problem which is known to admit a polynomial kernel when parameterized by the vertex cover number.

In a graph, a (perfect) matching cut is an edge cut that is a (perfect) matching. matching cut ( mc ), respectively, perfect matching cut ( pmc ), is the problem of deciding whether a given graph has a matching cut, respectively, a perfect matching cut. The disconnected perfect matching problem ( dpm ) is to decide if a graph has a perfect matching that contains a matching cut. Solving an open problem posed in [Lucke, Paulusma, Ries (ISAAC 2022, Algorithmica 2023)], we show that pmc is NP -complete in graphs without induced 14-vertex path P 14 . Our reduction also works simultaneously for mc and dpm , improving the previous hardness results of mc on P 15 -free graphs and of dpm on P 19 -free graphs to P 14 -free graphs for both problems. Actually, we prove a slightly stronger result: within P 14 -free 8-chordal graphs (graphs without chordless cycles of length at least 9), it is hard to distinguish between those without matching cuts (respectively, perfect matching cuts, disconnected perfect matchings) and those in which every matching cut is a perfect matching cut. Moreover, assuming the Exponential Time Hypothesis, none of these problems can be solved in 2 o ( n ) time for n -vertex P 14 -free 8-chordal graphs. On the positive side, we show that, as for mc [Moshi (JGT 1989)], dpm and pmc are polynomially solvable when restricted to 4-chordal graphs. Together with the negative results, this partly answers an open question on the complexity of pmc in k -chordal graphs asked in [Le, Telle (WG 2021, TCS 2022) & Lucke, Paulusma, Ries (MFCS 2023, TCS 2024)].

Abstract The well-known Cluster Vertex Deletion problem (cluster-vd) asks for a given graph G and an integer k whether it is possible to delete a set S of at most k vertices of G such that the resulting graph $$G-S$$ G - S is a cluster graph (a disjoint union of cliques). We give a complete characterization of graphs H for which cluster-vd on H-free graphs is polynomially solvable and for which it is $$\textsf{NP}$$ NP -complete. Moreover, in the $$\textsf{NP}$$ NP -completeness cases, cluster-vd cannot be solved in sub-exponential time in the vertex number of the H-free input graphs unless the Exponential-Time Hypothesis fails. We also consider the connected variant of cluster-vd, the Connected Cluster Vertex Deletion problem (connected cluster-vd), in which the set S has to induce a connected subgraph of G. It turns out that connected cluster-vd admits the same complexity dichotomy for H-free graphs. Our results enlarge a list of rare dichotomy theorems for well-studied problems on H-free graphs.

Abstract In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be $${\mathsf {NP}}$$ NP -complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is $${\mathsf {NP}}$$ NP -complete on graphs with minimum degree two. In this paper, we show that, for any given constant $$c>1$$ c > 1 , Matching Cut is $${\mathsf {NP}}$$ NP -complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant $$\epsilon >0$$ ϵ > 0 , Matching Cut remains $${\mathsf {NP}}$$ NP -complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree $$\delta >n^{1-\epsilon }$$ δ > n 1 - ϵ . We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree $$\delta \ge 3$$ δ ≥ 3 in $$O^*(\lambda ^n)$$ O ∗ ( λ n ) time, where $$\lambda$$ λ is the positive root of the polynomial $$x^{\delta +1}-x^{\delta }-1$$ x δ + 1 - x δ - 1 . Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is $$O^*(1.0099^n)$$ O ∗ ( 1 . 0099 n ) on graphs with minimum degree $$\delta \ge 469$$ δ ≥ 469 . Complementing our hardness results, we show that, for any two fixed constants $$1< c <4$$ 1 < c < 4 and $$c^{\prime }\ge 0$$ c ′ ≥ 0 , Matching Cut is solvable in polynomial time for graphs with large minimum degree $$\delta \ge \frac{1}{c}n-c^{\prime }$$ δ ≥ 1 c n - c ′ .

The square of a graph H, denoted H^2, is obtained from H by adding new edges between two distinct vertices whenever their distance in H is two. The half-squares of a bipartite graph B=(X,Y,E_B) are the subgraphs of B^2 induced by the color classes X and Y, B^2[X] and B^2[Y]. For a given graph G=(V,E_G), if G=B^2[V] for some bipartite graph B=(V,W,E_B), then B is a representation of G and W is the set of points in B. If in addition B is planar, then G is also called a map graph and B is a witness of G [Chen, Grigni, Papadimitriou. Map graphs. J. ACM , 49 (2) (2002) 127-138]. \nWhile Chen, Grigni, Papadimitriou proved that any map graph G=(V,E_G) has a witness with at most 3|V|-6 points, we show that, given a map graph G and an integer k, deciding if G admits a witness with at most k points is NP-complete. As a by-product, we obtain NP-completeness of edge clique partition on planar graphs; until this present paper, the complexity status of edge clique partition for planar graphs was previously unknown. \nWe also consider half-squares of tree-convex bipartite graphs and prove the following complexity dichotomy: Given a graph G=(V,E_G) and an integer k, deciding if G=B^2[V] for some tree-convex bipartite graph B=(V,W,E_B) with |W|<=k points is NP-complete if G is non-chordal dually chordal and solvable in linear time otherwise. Our proof relies on a characterization of half-squares of tree-convex bipartite graphs, saying that these are precisely the chordal and dually chordal graphs.

In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-complete even when restricted to bipartite graphs. It has been proved that Matching Cut is polynomially solvable for graphs of diameter two. In this paper, we show that, for any fixed integer d geq 4, Matching Cut is NP-complete in the class of graphs of diameter d. This almost resolves an open problem posed by Borowiecki and Jesse-Józefczyk in [Matching cutsets in graphs of diameter 2, Theoretical Computer Science 407 (2008) 574-582]. We then show that, for any fixed integer d geq 5, Matching Cut is NP-complete even when restricted to the class of bipartite graphs of diameter d. Complementing the hardness results, we show that Matching Cut is in polynomial-time solvable in the class of bipartite graphs of diameter at most three, and point out a new and simple polynomial-time algorithm solving Matching Cut in graphs of diameter 2.

In a graph G, a spanning tree T is called a tree t-spanner of G if the distance between any two vertices in T is at most t times their distance in G. While the complexity of finding a tree t-spanner of a given graph is known for any fixed t ≠ 3, the case t = 3 still remains open. In this article, we show that each directed path graph G has a tree 3-spanner T by means of a linear-time algorithm constructing T. Moreover, the output tree 3-spanner T is optimal in the sense that G has a tree 2-spanner if and only if T is a tree 2-spanner of G. © 1999 John Wiley & Sons, Inc. Networks 34: 81–87, 1999