20 citations · 75 across the 44 of their papers we have counts for
4 papers · 1 filter
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Matthew Johnson, Barnaby Martin, Sukanya Pandey +3
For any finite set of graphs, a graph is -subgraph-free if it does not contain any of as a subgraph. In recent work…
Partitioning H-Free Graphs of Bounded Diameter
Christoph Brause, Petr Golovach, Barnaby Martin +2
A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of -free graphs, that is, graphs that do n…
Acyclic, Star, and Injective Colouring: Bounding the Diameter
Christoph Brause, Petr Golovach, Barnaby Martin +3
We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a for…
Disconnected Cuts in Claw-free Graphs
Barnaby Martin, Daniel Paulusma, Erik Jan van Leeuwen
A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The decision problem whether a graph has a disconnected cut is called Disc…