D. Paulusma

activity

20212025

most citedComplexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem

2 citations · 4 across the 10 of their papers we have counts for

collaborators

Showing 2022Show all

3 papers · 1 filter

math.CO2022★ 2 cited

Matching Cuts in Graphs of High Girth and H-Free Graphs

Carl Feghali, Felicia Lucke, Daniel Paulusma +1

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…

cs.DM2022

Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs

Vadim Lozin, Barnaby Martin, Sukanya Pandey +4

For a fixed set $H$ of graphs, a graph $G$ is $H$ -subgraph-free if $G$ does not contain any $H \in H$ as a (not necessarily induced) subgraph. A recently propo…

math.CO2022

On The Complexity of Matching Cut for Graphs of Bounded Radius and $H$ -Free Graphs

Felicia Lucke, Daniël Paulusma, Bernard Ries

For a connected graph $G = (V, E)$ , a matching $M \subseteq E$ is a matching cut of $G$ if $G - M$ is disconnected. It is known that for an integer $d$ , the corresponding decision proble…

Matching Cuts in Graphs of High Girth and H-Free Graphs

Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs

On The Complexity of Matching Cut for Graphs of Bounded Radius and H-Free Graphs

On The Complexity of Matching Cut for Graphs of Bounded Radius and $H$ -Free Graphs