Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00225 On the threshold-width of graphs Maw-Shang Chang , Ling-Ju Hung , Ton Kloks , and Sheng-Lung Peng Vol. 15, no. 2, pp. 253-268, 2011. Regular paper Abstract For a graph class G, a graph G has G-width k if there are k independent sets \N1,...,\Nk 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 \Ni. 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.
|
Published: July 2011. Revised: March 2011. Submitted: September 2010. Final: May 2011. Accepted: April 2011. Reviewed: January 2011. Communicated by Dorothea Wagner |
| Journal of Graph Algorithms and Applications |