2 citations · 3 across the 14 of their papers we have counts for
17 papers · 1 filter
Greedy Coloring and Simple Exponential Strengthenings of Brooks-Type Theorems
Alex Crane, Carl Feghali, Felicia Lucke +2
Brooks' Theorem is a foundational result in graph coloring: if a graph is connected, not a clique, and has maximum degree , then it admits a proper -coloring. In this p…
Optimal b-Colourings and Fall Colourings in -Free Graphs
Jungho Ahn, Tala Eagling-Vose, Felicia Lucke +3
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…
Steiner Forest for -Subgraph-Free Graphs
Tala Eagling-Vose, David C. Kutner, Felicia Lucke +4
Our main result is a full classification, for every connected graph , of the computational complexity of Steiner Forest on -subgraph-free graphs. To obtain this dichotomy, we…
Colouring Graphs Without a Subdivided H-Graph: A Full Complexity Classification
Tala Eagling-Vose, Jorik Jooken, Felicia Lucke +2
We consider Colouring on graphs that are -subgraph-free for some fixed graph , which are graphs that do not contain as a subgraph. To classify the complexity of Colouring…
Finding d-Cuts in Claw-free Graphs
Jungho Ahn, Tala Eagling-Vose, Felicia Lucke +2
The Matching Cut problem is to decide if the vertex set of a connected graph can be partitioned into two non-empty sets and such that the edges between and form a m…
Finding Minimum Matching Cuts in -free Graphs
Felicia Lucke, Joseph Marchand, Jannik Olbrich
A matching cut is a matching that is also an edge cut. In the problem Minimum Matching Cut, we ask for a matching cut with the minimum number of edges in the matching. We investiga…
Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter
Felicia Lucke
In the Matching Cut problem we ask whether a graph has a matching cut, that is, a matching which is also an edge cut of . We consider the variants Perfect Matching Cut and D…
A (simple) proof of the rna conjecture on powers of cycles
Carl Feghali, Felicia Lucke
We verify a recent conjecture of Sehrawat, Kumar and Ahlawat on the minimum bisection width (a notion that was rediscovered in 2020 by Acharya and Kureethara under the name of rna…
Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
Felicia Lucke, Ali Momeni, Daniël Paulusma +1
The d-Cut problem is to decide if a graph has an edge cut such that each vertex has at most d neighbours at the opposite side of the cut. If , we obtain the intensively studie…
Maximizing Matching Cuts
Van Bang Le, Felicia Lucke, Daniël Paulusma +1
A matching cut in a graph G is an edge cut of G that is also a matching. This short survey gives an overview of old and new results and open problems for Maximum Matching Cut, whic…
On Blockers and Transversals of Maximum Independent Sets in Co-Comparability Graphs
Felicia Lucke, Bernard Ries
In this paper, we consider the following two problems: (i) Deletion Blocker() where we are given an undirected graph and two integers and ask whether there…
Dichotomies for Maximum Matching Cut: -Freeness, Bounded Diameter, Bounded Radius
Felicia Lucke, Daniël Paulusma, Bernard Ries
The (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 Perfe…
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 …