Blar i Department of Informatics på forfatter "Brause, Christoph"
-
Acyclic, star, and injective colouring: bounding the diameter∗
Brause, Christoph; Golovach, Petr; Martin, Barnaby; Ochem, Pascal; Paulusma, Daniël; Smith, Siani (Journal article; Peer reviewed, 2022)We examine the effect of bounding the diameter for a number of natural and well-studied variants of the COLOURING problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest ... -
Partitioning H-Free Graphs of Bounded Diameter
Brause, Christoph; Golovach, Petr; Martin, Barnaby; Paulusma, Daniël; Smith, Siani (Journal article; Peer reviewed, 2021)A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, ...