Matthew Johnson

activity

20142025

most citedA Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs

25 citations · 79 across the 15 of their papers we have counts for

collaborators

Showing 2014Show all

3 papers · 1 filter

cs.CC2014★ 8 cited

Narrowing the Complexity Gap for Colouring ( $C_{s}$ , $P_{t}$ )-Free Graphs

Shenwei Huang, Matthew Johnson, Daniël Paulusma

For a positive integer $k$ and graph $G = (V, E)$ , a $k$ -colouring of $G$ is a mapping $c : V \to {1, 2, \dots, k}$ such that $c (u) \neq = c (v)$ whenever $uv \in E$ . The $k$ -Colourin…

cs.CC2014★ 25 cited

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 $k$ , a $k$ -colouring of a graph $G = (V, E)$ is a mapping $c : V \to {1, 2, ..., k}$ such that $c (u) \neq = c (v)$ whenever $uv \in E$ . The Colouring problem is…

cs.CC2014★ 2 cited

Finding Shortest Paths between Graph Colourings

Matthew Johnson, Dieter Kratsch, Stefan Kratsch +2

The $k$ -colouring reconfiguration problem asks whether, for a given graph $G$ , two proper $k$ -colourings $α$ and $β$ of $G$ , and a positive integer $ℓ$ , there exists a sequence…

Narrowing the Complexity Gap for Colouring (Cs​,Pt​)-Free Graphs

A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs

Finding Shortest Paths between Graph Colourings

Narrowing the Complexity Gap for Colouring ( $C_{s}$ , $P_{t}$ )-Free Graphs