38 citations · 246 across the 68 of their papers we have counts for
14 papers · 1 filter
On Colouring -Free and -Free Graphs
Konrad Dabrowski, Daniel Paulusma
The Colouring problem asks whether the vertices of a graph can be coloured with at most colours for a given integer in such a way that no two adjacent vertices receive the…
Connected Vertex Cover for -Free Graphs
Matthew Johnson, Giacomo Paesani, Daniel Paulusma
The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most that induces a connected subgraph of . This is a well-studied problem, known…
Clique-width and Well-Quasi-Ordering of Triangle-Free Graph Classes
Konrad K. Dabrowski, Vadim V. Lozin, Daniël Paulusma
Daligault, Rao and Thomassé asked whether every hereditary graph class that is well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamar…
Surjective H-Colouring over Reflexive Digraphs
Benoit Larose, Barnaby Martin, Daniel Paulusma
The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for…
Independent Feedback Vertex Set for -free Graphs
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali +2
The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer , to delete at most vertices from a given graph so t…
Independent Feedback Vertex Sets for Graphs of Bounded Diameter
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali +2
The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets and , where is an independent set and induces…