4 citations · 6 across the 13 of their papers we have counts for
18 papers · 1 filter
Identification to Subclasses of Chordal Graphs
Petr A. Golovach, Laure Morelle, Daniël Paulusma
An identification of two vertices and in a graph replaces them with a new vertex whose neighborhood is the union of the neighborhoods of and . We study the {\sc ${\c…
Finding -Cuts in Probe -Free Graphs
Konrad K. Dabrowski, Tala Eagling-Vose, Matthew Johnson +2
For an integer , the -Cut problem is that of deciding whether a graph has an edge cut in which each vertex is adjacent to at most vertices on the opposite side of t…
Colouring Probe -Free Graphs
Daniël Paulusma, Johannes Rauch, Erik Jan van Leeuwen
The NP-complete problems Colouring and k-Colouring ) are well studied on -free graphs, i.e., graphs that do not contain some fixed graph as an induced subgraph. We…
An Algorithmic Framework for Locally Constrained Homomorphisms
Laurent Bulteau, Konrad K. Dabrowski, Noleen Köhler +2
A homomorphism from a guest graph to a host graph is locally bijective, injective or surjective if for every , the restriction of to the neighbourhood of…
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…
Induced Disjoint Paths in AT-free Graphs
Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen
Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices (except perhaps their end-ve…