25 citations · 34 across the 16 of their papers we have counts for
7 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…
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…
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…
Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali +2
We continue research into a well-studied family of problems that ask whether the vertices of a graph can be partitioned into sets and~, where is an independent set and $…
Contracting Bipartite Graphs to Paths and Cycles
Konrad K. Dabrowski, Daniël Paulusma
Testing if a given graph contains the -vertex path as a minor or as an induced minor is trivial for every fixed integer . However, the situation changes for t…