4 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…
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…
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…
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…