On the threshold-width of graphs

Abstract

For a graph class G, a graph G has G-width k if there are k independent sets \N₁,...,\N_k in G such that G can be embedded into a graph H ∈ G 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 \N_i. For the class \T\H of threshold graphs we show that \T\H-width is NP-complete and we present fixed-parameter algorithms. We also show that for each k, graphs of \T\H-width at most k are characterized by a finite collection of forbidden induced subgraphs.