On the threshold-width of graphs
From MaRDI portal
Publication:6236827
arXiv1210.8365MaRDI QIDQ6236827FDOQ6236827
Authors: Moonjeong Chang, Linda Hung, Ton Kloks, Shou-Li Peng 
Publication date: 29 October 2012
Abstract: The GG-width of a class of graphs GG is defined as follows. A graph G has GG-width k if there are k independent sets N1,...,Nk in G such that G can be embedded into a graph H in GG such that for every edge e in H which is not an edge in G, there exists an i such that both endpoints of e are in Ni. For the class TH of threshold graphs we show that TH-width is NP-complete and we present fixed-parameter algorithms. We also show that for each k, graphs of TH-width at most k are characterized by a finite collection of forbidden induced subgraphs.
This page was built for publication: On the threshold-width of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6236827)
