5 papers
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…
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs
Jan Bok, Nikola Jedlickova, Barnaby Martin +3
A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injec…
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…
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…
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…