38 citations · 246 across the 68 of their papers we have counts for
12 papers · 1 filter
Induced Disjoint Paths in AT-free Graphs
Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen
Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices (except perhaps their end-ve…
Hard Problems That Quickly Become Very Easy
Barnaby Martin, Daniël Paulusma, Siani Smith
A graph class is hereditary if it is closed under vertex deletion. We give examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become constant-time solvable fo…
The complexity of L(p,q)-Edge-Labelling
Gaetan Berthe, Barnaby Martin, Daniel Paulusma +1
We consider the L(p,q)-Edge-Labelling problem, which is the edge variant of the well-known L(p,q)-Labelling problem. So far, the complexity of this problem was only partially class…
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…
Solving Problems on Generalized Convex Graphs via Mim-Width
Flavia Bonomo-Braberman, Nick Brettell, Andrea Munaro +1
A bipartite graph is -convex, for some family of graphs , if there exists a graph with such that the set of neighbours in $…
List -Colouring -Free Graphs: a Mim-width Perspective
Nick Brettell, Jake Horsfield, Andrea Munaro +1
A colouring of a graph is a mapping such that for every two adjacent vertices and of . The {\sc List -Colourin…