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 · math.COShow all

2 papers · 2 filters

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…

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…