3 citations · 8 across the 17 of their papers we have counts for
6 papers · 1 filter
Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter
Barnaby Martin, Daniel Paulusma, Siani Smith
For a fixed integer, the -Colouring problem is to decide if the vertices of a graph can be coloured with at most colours for an integer , such that no two adjacent vertic…
Disjoint Paths and Connected Subgraphs for H-Free Graphs
Walter Kern, Barnaby Martin, Daniël Paulusma +2
The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We deter…
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…
QCSP on Reflexive Tournaments
Benoit Larose, Petar Markovic, Barnaby Martin +3
We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split…
Colouring Graphs of Bounded Diameter in the Absence of Small Cycles
Barnaby Martin, Daniel Paulusma, Siani Smith
For , a -colouring of is a mapping from to such that for any two non-adjacent vertices and . The -Colouring…