38 citations · 246 across the 68 of their papers we have counts for
41 papers · 1 filter
Identification to Subclasses of Chordal Graphs
Petr A. Golovach, Laure Morelle, Daniël Paulusma
An identification of two vertices and in a graph replaces them with a new vertex whose neighborhood is the union of the neighborhoods of and . We study the {\sc ${\c…
Finding -Cuts in Probe -Free Graphs
Konrad K. Dabrowski, Tala Eagling-Vose, Matthew Johnson +2
For an integer , the -Cut problem is that of deciding whether a graph has an edge cut in which each vertex is adjacent to at most vertices on the opposite side of t…
Colouring Probe -Free Graphs
Daniël Paulusma, Johannes Rauch, Erik Jan van Leeuwen
The NP-complete problems Colouring and k-Colouring ) are well studied on -free graphs, i.e., graphs that do not contain some fixed graph as an induced subgraph. We…
The Complexity of Diameter on H-free graphs
Jelle J. Oostveen, Daniël Paulusma, Erik Jan van Leeuwen
The intensively studied Diameter problem is to find the diameter of a given connected graph. We investigate, for the first time in a structured manner, the complexity of Diameter f…
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Matthew Johnson, Barnaby Martin, Sukanya Pandey +3
For any finite set of graphs, a graph is -subgraph-free if it does not contain any of as a subgraph. In recent work…
An Algorithmic Framework for Locally Constrained Homomorphisms
Laurent Bulteau, Konrad K. Dabrowski, Noleen Köhler +2
A homomorphism from a guest graph to a host graph is locally bijective, injective or surjective if for every , the restriction of to the neighbourhood of…
Classifying Subset Feedback Vertex Set for -Free Graphs
Giacomo Paesani, Daniël Paulusma, Paweł Rzążewski
In the Feedback Vertex Set problem, we aim to find a small set of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires to intersect…
Partitioning H-Free Graphs of Bounded Diameter
Christoph Brause, Petr Golovach, Barnaby Martin +2
A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of -free graphs, that is, graphs that do n…
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs
Giacomo Paesani, Daniël Paulusma, Paweł Rzążewski
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on -free graphs, that is, graphs that do not contain some fixed graph as an induced subgra…
Acyclic, Star, and Injective Colouring: Bounding the Diameter
Christoph Brause, Petr Golovach, Barnaby Martin +3
We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a for…
Induced Disjoint Paths in AT-free Graphs
Petr A. Golovach, Daniël Paulusma, Erik Jan van Leeuwen
Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices (except perhaps their end-ve…
Solving Problems on Generalized Convex Graphs via Mim-Width
Flavia Bonomo-Braberman, Nick Brettell, Andrea Munaro +1
A bipartite graph is -convex, for some family of graphs , if there exists a graph with such that the set of neighbours in $…
List -Colouring -Free Graphs: a Mim-width Perspective
Nick Brettell, Jake Horsfield, Andrea Munaro +1
A colouring of a graph is a mapping such that for every two adjacent vertices and of . The {\sc List -Colourin…
Computing Weighted Subset Transversals in -Free Graphs
Nick Brettell, Matthew Johnson, Daniel Paulusma
For the Odd Cycle Transversal problem, the task is to find a small set of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal proble…
Colouring -Free Graphs: a Mim-Width Perspective
Nick Brettell, Jake Horsfield, Daniel Paulusma
We prove that the class of -free graphs has bounded mim-width for every and , and that there is a polynomial-time algorithm that, given a graph i…
Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective
Hans Bodlaender, Nick Brettell, Matthew Johnson +3
We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced…
Bounding the Mim-Width of Hereditary Graph Classes
Nick Brettell, Jake Horsfield, Andrea Munaro +2
A large number of NP-hard graph problems become polynomial-time solvable on graph classes where the mim-width is bounded and quickly computable. Hence, when solving such problems o…
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest
Konrad K. Dabrowski, Carl Feghali, Matthew Johnson +3
A graph is -free if it contains no induced subgraph isomorphic to . We prove new complexity results for the two classical cycle transversal problems Feedback Vertex Set and O…
Classifying k-Edge Colouring for H-free Graphs
Esther Galby, Paloma T. Lima, Daniel Paulusma +1
A graph is -free if it does not contain an induced subgraph isomorphic to . For every integer and every graph , we determine the computational complexity of -Edge C…
Contracting to a Longest Path in H-Free Graphs
Walter Kern, Daniel Paulusma
We prove two dichotomy results for detecting long paths as patterns in a given graph. The NP-hard problem Longest Induced Path is to determine the longest induced path in a graph.…
Finding a Small Number of Colourful Components
Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin +3
A partition of the vertex set of a graph with a (not necessarily proper) colouring is colourful if no two vertices in any have the same colour and…
Colouring -Free Graphs
Tereza Klimošová, Josef Malík, Tomáš Masařík +3
The -Colouring problem is to decide if the vertices of a graph can be coloured with at most colours for a fixed integer such that no two adjacent vertices are coloured a…
Disconnected Cuts in Claw-free Graphs
Barnaby Martin, Daniel Paulusma, Erik Jan van Leeuwen
A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The decision problem whether a graph has a disconnected cut is called Disc…
Connected Vertex Cover for -Free Graphs
Matthew Johnson, Giacomo Paesani, Daniel Paulusma
The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most that induces a connected subgraph of . This is a well-studied problem, known…