38 citations · 246 across the 68 of their papers we have counts for
5 papers · 1 filter
Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes
Konrad K. Dabrowski, Vadim V. Lozin, Daniël Paulusma
Daligault, Rao and Thomassé asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev rece…
Squares of Low Maximum Degree
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach +3
A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of decid…
A Linear Kernel for Finding Square Roots of Almost Planar Graphs
Petr A. Golovach, Dieter Kratsch, Daniël Paulusma +1
A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 from each other. The Square Root p…
Hereditary Graph Classes: When the Complexities of Colouring and Clique Cover Coincide
Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson +1
A graph is -free for a pair of graphs if it contains no induced subgraph isomorphic to or . In 2001, Král', Kratochv\'ıl, Tuza, and Woeginger initia…
New Bounds for the Snake-in-the-Box Problem
David Allison, Daniel Paulusma
The Snake-in-the-Box problem is that of finding a longest induced path in an -dimensional hypercube. We prove new lower bounds for the values . The Coil-in-th…