6 papers
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…
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…
Clique-Width for Graph Classes Closed under Complementation
Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson +3
Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite)…