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

2 papers · 1 filter

math.CO2023★ 2 cited

Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem

Hans L. Bodlaender, Matthew Johnson, Barnaby Martin +5

We study Steiner Forest on $H$ -subgraph-free graphs, that is, graphs that do not contain some fixed graph $H$ as a (not necessarily induced) subgraph. We are motivated by a recent…

cs.DS2023

Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs

Matthew Johnson, Barnaby Martin, Sukanya Pandey +3

For any finite set $H = {H_{1}, \dots, H_{p}}$ of graphs, a graph is $H$ -subgraph-free if it does not contain any of $H_{1}, \dots, H_{p}$ as a subgraph. In recent work…