5 papers · 1 filter
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…