Blar i Bergen Open Research Archive på forfatter "Paulusma, Daniël"
-
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 ... -
Editing to Eulerian Graphs
Dabrowski, Konrad K.; Golovach, Petr; van' t Hof, Pim; Paulusma, Daniël (Journal article; Peer reviewed, 2014)We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let ea, ed and vd denote the operations edge addition, edge deletion and ... -
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, ...