38 citations · 246 across the 68 of their papers we have counts for
9 papers · 1 filter
Editing to Eulerian Graphs
Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof +1
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 , and denote t…
Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree
Steven Chaplick, Jiří Fiala, Pim van 't Hof +2
A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or i…
Narrowing the Complexity Gap for Colouring (,)-Free Graphs
Shenwei Huang, Matthew Johnson, Daniël Paulusma
For a positive integer and graph , a -colouring of is a mapping such that whenever . The -Colourin…
A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
Petr A. Golovach, Matthew Johnson, Daniël Paulusma +1
For a positive integer , a -colouring of a graph is a mapping such that whenever . The Colouring problem is…
Bounding Clique-Width via Perfect Graphs
Konrad K. Dabrowski, Shenwei Huang, Daniël Paulusma
Given two graphs and , a graph is -free if it contains no subgraph isomorphic to or . We continue a recent study into the clique-width of $(H_1…
Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs
Konrad K. Dabrowski, Daniël Paulusma
If a graph has no induced subgraph isomorphic to any graph in a finite family , it is said to be -free. The class of -free graphs has bound…