Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00225
On the thresholdwidth of graphs
MawShang Chang,
LingJu Hung,
Ton Kloks, and
ShengLung Peng
Vol. 15, no. 2, pp. 253268, 2011. Regular paper.
Abstract For a graph class G, a graph G has Gwidth
k if there are k independent sets
\N_{1},...,\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\Hwidth is NPcomplete
and we present fixedparameter algorithms. We also show that for
each k, graphs of \T\Hwidth 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

Journal Supporters
