25 citations · 109 across the 80 of their papers we have counts for
5 papers · 1 filter
The Parameterized Complexity of Graph Cyclability
Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis +1
The cyclability of a graph is the maximum integer for which every vertices lie on a cycle. The algorithmic version of the problem, given a graph and a non-negative inte…
Editing to Eulerian Graphs
Konrad K. Dabrowski, Petr A. Golovach, Pim van 't Hof +1
We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let , and denote t…
A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
Petr A. Golovach, Matthew Johnson, Daniël Paulusma +1
For a positive integer , a -colouring of a graph is a mapping such that whenever . The Colouring problem is…
Hadwiger number of graphs with small chordality
Petr A. Golovach, Pinar Heggernes, Pim van 't Hof +1
The Hadwiger number of a graph G is the largest integer h such that G has the complete graph K_h as a minor. We show that the problem of determining the Hadwiger number of a graph…
Induced Disjoint Paths in Circular-Arc Graphs in Linear Time
Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen
The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i connects s_i and t_i for i=1,..…