Home Issues About JGAA Instructions for Authors
 
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.
Submitted: September 2010.
Reviewed: January 2011.
Revised: March 2011.
Accepted: April 2011.
Final: May 2011.
Published: July 2011.
Communicated by Dorothea Wagner
article (PDF)
BibTeX