2 citations · 3 across the 14 of their papers we have counts for
16 papers
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…