-
Chapter and Conference Paper
Cutting Barnette Graphs Perfectly is Hard
A perfect matching cut is a perfect matching that is also a cutset, or equivalently a perfect matching containing an even number of edges on every cycle. The corresponding algorithmic problem, Perfect Matching Cu...
-
Chapter and Conference Paper
s-Club Cluster Vertex Deletion on Interval and Well-Partitioned Chordal Graphs
In this paper, we study the computational complexity of s -Club Cluster Vertex Deletion. Given a graph, s -Club Cluster Vertex Deletion (s -CVD) aims to delete the minimum number of vertices from the graph so th...
-
Chapter and Conference Paper
Algorithms and Complexity of s-Club Cluster Vertex Deletion
An s-club is a graph which has diameter at most s. Let G be a graph. A set of vertices \(D\subseteq V(G)\) ...
-
Chapter and Conference Paper
Dominating Set on Overlap Graphs of Rectangles Intersecting a Line
A graph \(G = (V, E)\) is called a rectangle overlap graph if there is a bijection between V and a set ...
-
Chapter and Conference Paper
On Rectangle Intersection Graphs with Stab Number at Most Two
Rectangle intersection graphs are the intersection graphs of axis-parallel rectangles in the plane. A graph G is said to be a k-stabbable rectangle intersection graph, or k-SRIG for short, if it has a rectangle i...
-
Chapter and Conference Paper
On Local Structures of Cubicity 2 Graphs
A 2-stab unit interval graph (2SUIG) is an axes-parallel unit square intersection graph where the unit squares intersect either of the two fixed lines parallel to the X-axis, distance
-
Chapter and Conference Paper
On a Special Class of Boxicity 2 Graphs
We define and study a class of graphs, called 2-stab interval graphs (2SIG), with boxicity 2 which properly contains the class of interval graphs. A 2SIG is an axes-parallel rectangle intersection graph where ...