The tree- and clique-width of bipartite graphs in special classes

被引：0

作者：

Lozin, V. V. ^{[1
]}

Rautenbach, D. ^{[2
]}

机构：

[1] Rutgers State Univ, RUTCOR, 640 Bartholomew Rd, Piscataway, NJ 08854 USA

[2] Univ Bonn, Forsch Inst Diskrete Math, D-53113 Bonn, Germany

来源：

AUSTRALASIAN JOURNAL OF COMBINATORICS | 2006年 / 34卷

关键词：

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The tree- and clique-width are two graph parameters which are of primary importance in algorithmic graph theory because of the fact that many NP -hard graph problems admit polynomial-time solutions when restricted to graphs of bounded tree- or clique-width. Both parameters are known to be unbounded in the class of all bipartite graphs. We study the tree- and clique-width of bipartite graphs in special classes. The main result is a necessary condition for the tree- and clique-width to be bounded in subclasses of bipartite graphs defined by finitely many forbidden induced bipartite subgraphs. We use this result to analyze the tree- and clique-width of bipartite graphs in classes defined by a single forbidden induced subgraph.

引用

页码：57 / 67

页数：11

共 11 条

[1]

Boliac R, 2002, LECT NOTES COMPUT SC, V2518, P44

[2]

Boliac R., 2001, DISCUSSIONES MATH GR, P293

[3]

Brandstadt A, 2003, ARS COMBINATORIA, V67, P273

[4] Upper bounds to the clique width of graphs [J].

Courcelle, B ;

Olariu, S .

DISCRETE APPLIED MATHEMATICS, 2000, 101 (1-3) :77-114

[5]

Fouquet J.-L., 1999, International Journal of Foundations of Computer Science, V10, P513, DOI 10.1142/S0129054199000368

[6] Bi-complement reducible graphs [J].

Giakoumakis, V ;

Vanherpe, JM .

ADVANCES IN APPLIED MATHEMATICS, 1997, 18 (04) :389-402

[7]

Golumbic M. C., 2000, International Journal of Foundations of Computer Science, V11, P423, DOI 10.1142/S0129054100000260

[8] Chordal bipartite graphs of bounded tree- and clique-width [J].

Lozin, V ;

Rautenbach, D .

DISCRETE MATHEMATICS, 2004, 283 (1-3) :151-158

[9] Bipartite graphs without a skew star [J].

Lozin, VV .

DISCRETE MATHEMATICS, 2002, 257 (01) :83-100

[10] Modular decomposition and transitive orientation [J].

McConnell, RM ;

Spinrad, JP .

DISCRETE MATHEMATICS, 1999, 201 (1-3) :189-241

← 1 2 →