2 citations · 3 across the 14 of their papers we have counts for
5 papers · 1 filter
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…
Reducing Graph Parameters by Contractions and Deletions
Felicia Lucke, Felix Mann
We consider the following problem: for a given graph and two integers and , can we apply a fixed graph operation at most times in order to reduce a given graph param…
Finding Matching Cuts in -Free Graphs
Felicia Lucke, Daniël Paulusma, Bernard Ries
The NP-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…
On The Complexity of Matching Cut for Graphs of Bounded Radius and -Free Graphs
Felicia Lucke, Daniël Paulusma, Bernard Ries
For a connected graph , a matching is a matching cut of if is disconnected. It is known that for an integer , the corresponding decision proble…
Using Edge Contractions and Vertex Deletions to Reduce the Independence Number and the Clique Number
Felicia Lucke, Felix Mann
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 …