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
|
Journal Supporters
|