Cluster Vertex Deletion on 2-thin and proper 2-thin graphs

NINA PARDAL

Workshop; Graph Width Parameters: from Structure to Algorithms; 2021

Queen's University Belfast-Durham University-UBA-Victoria University of Wellington

Graphs with bounded thinness were defined in 2007 as a generalization of interval graphs, which are precisely those graphs with thinness 1. Further on, in 2018, proper k-thin graphs were defined in an analogous way as a generalization of proper interval graphs. When a representation of the graph as a k-thin graph is given for some constant value k, some NP-complete problems as maximum weighted independent set and bounded coloring with fixed number of colors can be solved in polynomial time.Having this in mind, we want to study the complexity of the Cluster Vertex Deletion problem (known to be NP-complete) on 2-thin and proper 2-thin graphs. This is, when the input graph is a graph with thinness (resp. proper thinness) 2.