10 citations · 23 across the 31 of their papers we have counts for
3 papers · 2 filters
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…