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 2015Show all

6 papers · 1 filter

math.CO2015

What Graphs are 2-Dot Product Graphs?

Matthew Johnson, Daniel Paulusma, Erik Jan van Leeuwen

Let $d \geq 1$ be an integer. From a set of $d$ -dimensional vectors, we obtain a $d$ -\dpg\ by letting each vector $\va^u$ correspond to a vertex $u$ and by adding an edge between t…

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…

math.CO2015

Erdős-Ko-Rado Theorems for a Family of Trees

Carl Feghali, Matthew Johnson, Daniel Thomas

Given a graph $G$ and an integer $r \geq 1$ , let $I^{(r)} (G)$ denote the family of independent sets of size $r$ of $G$ . For a vertex $v$ of $G$ , let $\mathcal{I}^{(r)}_v(G…

cs.DS2015

Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

Konrad K. Dabrowski, Francois Dross, Matthew Johnson +1

A colouring of a graph $G = (V, E)$ is a function $c : V \to {1, 2, \dots}$ such that $c (u) \neq = c (v)$ for every $uv \in E$ . A $k$ -regular list assignment of $G$ is a function $L…

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…

cs.CC2015

A Reconfigurations Analogue of Brooks' Theorem and its Consequences

Carl Feghali, Matthew Johnson, Daniël Paulusma

Let $G$ be a simple undirected graph on $n$ vertices with maximum degree~ $Δ$ . Brooks' Theorem states that $G$ has a $Δ$ -colouring unless~ $G$ is a complete graph, or a cycle with an…