On the threshold-width of graphs - Chang, Maw-Shang; Hung, Ling-Ju; Kloks, Ton; Peng, Sheng-Lung (Journal of Graph Algorithms and Applications, 2011)
For a graph class G, a graph G has G-widthk if there are k independent sets\N1,...,\Nk in G such that G can beembedded into a graph H ∈ G such that for every edgee in H which is not an edge in G, there exists an i suchthat both endpoints of e are in \Ni. For the class\T\H of threshold graphs we show that \T\H-width is NP-completeand we present fixed-parameter algorithms. We also show that foreach k, graphs of \T\H-width at most k are characterized by afinite collection of forbidden induced subgraphs. <!---->