38 citations · 246 across the 68 of their papers we have counts for
13 papers · 1 filter
Non-crossing -graphs: a generalization of proper interval graphs admitting FPT algorithms
Flavia Bonomo-Braberman, Nick Brettell, Noleen Köhler +2
We prove new parameterized complexity results for the FO Model Checking problem on a well-known generalization of interval and circular-arc graphs: the class of -graphs, for any…
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
Matthew Johnson, Barnaby Martin, Siani Smith +3
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree (also known as subcubic graphs). This improves…
QCSP on Reflexive Tournaments
Benoit Larose, Petar Markovic, Barnaby Martin +3
We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split…
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…
On Colouring -Free and -Free Graphs
Konrad Dabrowski, Daniel Paulusma
The Colouring problem asks whether the vertices of a graph can be coloured with at most colours for a given integer in such a way that no two adjacent vertices receive the…
Surjective H-Colouring over Reflexive Digraphs
Benoit Larose, Barnaby Martin, Daniel Paulusma
The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for…
Critical Vertices and Edges in -free Graphs
Daniël Paulusma, Christophe Picouleau, Bernard Ries
A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by 1. We consider the problems of deciding whether a graph has a critical vertex o…
Surjective H-Colouring: New Hardness Results
Petr Golovach, Matthew Johnson. Barnaby Martin, Daniel Paulusma +1
A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H when…
A Reconfigurations Analogue of Brooks' Theorem and its Consequences
Carl Feghali, Matthew Johnson, Daniël Paulusma
Let be a simple undirected graph on vertices with maximum degree~. Brooks' Theorem states that has a -colouring unless~ is a complete graph, or a cycle with an…
Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree
Steven Chaplick, Jiří Fiala, Pim van 't Hof +2
A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or i…
Narrowing the Complexity Gap for Colouring (,)-Free Graphs
Shenwei Huang, Matthew Johnson, Daniël Paulusma
For a positive integer and graph , a -colouring of is a mapping such that whenever . The -Colourin…
A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
Petr A. Golovach, Matthew Johnson, Daniël Paulusma +1
For a positive integer , a -colouring of a graph is a mapping such that whenever . The Colouring problem is…
Finding Shortest Paths between Graph Colourings
Matthew Johnson, Dieter Kratsch, Stefan Kratsch +2
The -colouring reconfiguration problem asks whether, for a given graph , two proper -colourings and of , and a positive integer , there exists a sequence…