25 citations · 109 across the 80 of their papers we have counts for
5 papers · 1 filter
Kernelizing Temporal Exploration Problems
Emmanuel Arrighi, Fedor V. Fomin, Petr Golovach +1
We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs that s…
Recognizing Proper Tree-Graphs
Steven Chaplick, Petr A. Golovach, Tim A. Hartmann +1
We investigate the parameterized complexity of the recognition problem for the proper -graphs. The -graphs are the intersection graphs of connected subgraphs of a subdivision…
Partial complementation of graphs
Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme +1
A partial complement of the graph is a graph obtained from by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for…
Surjective H-Colouring: New Hardness Results
Petr Golovach, Matthew Johnson. Barnaby Martin, Daniel Paulusma +1
A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H when…
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…