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 2015 · cs.DMShow all

2 papers · 2 filters

cs.DM2015

On a conjecture of Mohar concerning Kempe equivalence of regular graphs

Marthe Bonamy, Nicolas Bousquet, Carl Feghali +1

Let $G$ be a graph with a vertex colouring $α$ . Let $a$ and $b$ be two colours. Then a connected component of the subgraph induced by those vertices coloured either $a$ or $b$ is k…

cs.DM2015

Kempe Equivalence of Colourings of Cubic Graphs

Carl Feghali, Matthew Johnson, Daniel Paulusma

Given a graph $G = (V, E)$ and a proper vertex colouring of $G$ , a Kempe chain is a subset of $V$ that induces a maximal connected subgraph of $G$ in which every vertex has one of two…