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

2 papers · 1 filter

cs.DM2018★ 1 cited

Graph Isomorphism for $(H_{1}, H_{2})$ -free Graphs: An Almost Complete Dichotomy

Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski +3

We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs $H_{1}$ and $H_{2}$ for all but six pairs $(H_1,H_2)…

cs.DS2018

Finding a Small Number of Colourful Components

Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin +3

A partition $(V_{1}, \dots, V_{k})$ of the vertex set of a graph $G$ with a (not necessarily proper) colouring $c$ is colourful if no two vertices in any $V_{i}$ have the same colour and…

Graph Isomorphism for (H1​,H2​)-free Graphs: An Almost Complete Dichotomy

Finding a Small Number of Colourful Components

Graph Isomorphism for $(H_{1}, H_{2})$ -free Graphs: An Almost Complete Dichotomy