25 citations · 79 across the 15 of their papers we have counts for
5 papers · 1 filter
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…
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…