10 papers
: Truly Linear FPT
Benjamin Merlin Bumpus, Rod Downey, Tala Eagling-Vose +7
Parameterized complexity has always been concerned with practical computing: by confining combinatorial explosion to a secondary parameter , one can uncover why and how many NP-…
On Detecting -Induced Minors for Small
Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma +1
We consider the -Induced Minor problem: for a fixed graph~, decide whether a given graph contains as an induced minor. While the problem is known to be NP-complete fo…
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 -Cuts in Probe -Free Graphs
Konrad K. Dabrowski, Tala Eagling-Vose, Matthew Johnson +2
For an integer , the -Cut problem is that of deciding whether a graph has an edge cut in which each vertex is adjacent to at most vertices on the opposite side of t…
Bounding Width on Graph Classes of Constant Diameter
Konrad K. Dabrowski, Tala Eagling-Vose, Noleen Köhler +2
We determine if the width of a graph class changes from unbounded to bounded if we consider only those graphs from whose diameter is bounded. As parameters we…
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…
Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma +1
We continue the study of the recently-introduced C123-framework, for (simple) graph problems restricted to inputs specified by the forbidding of some finite set of subgraphs, to mo…
Graph Homomorphism, Monotone Classes and Bounded Pathwidth
Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma +1
In recent work by Johnson et al. (2022), a framework was described for the study of graph problems over classes specified by omitting each of a finite set of graphs as subgraphs. I…