Decomposition of odd-hole-free graphs by double star cutsets and 2-joins

被引：17
作者：
Conforti, M
Cornuéjols, G
Vuskovic, K
机构：
[1] Univ Padua, Dipartimento Matemat Pura & Applicata, I-35131 Padua, Italy
[2] Carnegie Mellon Univ, GSIA, Pittsburgh, PA 15213 USA
[3] Univ Marseille, LIF, F-13288 Marseille, France
[4] Univ Leeds, Sch Comp, Leeds LS2 9JT, W Yorkshire, England
来源：
DISCRETE APPLIED MATHEMATICS | 2004年 / 141卷 / 1-3期
关键词：
odd-hole-free graphs; even-signable graphs; decomposition; 2-join; double star cutset;
D O I：
10.1016/S0166-218X(03)00364-0
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper we decompose odd-hole-free graphs (graphs that do not contain as an induced subgraph a chordless cycle of odd length greater than three) with double star cutsets and 2-joins into bipartite graphs, line graphs of bipartite graphs and the complements of line graphs of bipartite graphs. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码：41 / 91
页数：51
相关论文
共 12 条
[1]  
[Anonymous], THESIS U WATERLOO
[2]  
CHUDNOVSKY M, 2002, STRONG PERFECT GRAPH
[3]   STAR-CUTSETS AND PERFECT GRAPHS [J].
CHVATAL, V .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 39 (03) :189-199
[4]   Graphs without odd holes, parachutes or proper wheels:: a generalization of Meyniel graphs and of line graphs of bipartite graphs [J].
Conforti, M ;
Cornuéjols, G .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 87 (02) :300-330
[5]   Even-hole-free graphs Part II:: Recognition algorithm [J].
Conforti, M ;
Cornuëjols, G ;
Kapoor, A ;
Vuskovic, K .
JOURNAL OF GRAPH THEORY, 2002, 40 (04) :238-266
[6]   Even-hole-free graphs part I:: Decomposition theorem [J].
Conforti, M ;
Cornuéjols, G ;
Kapoor, A ;
Vuskovic, K .
JOURNAL OF GRAPH THEORY, 2002, 39 (01) :6-49
[7]   Perfect graphs, partitionable graphs and cutsets [J].
Conforti, M ;
Cornuéjols, G ;
Gasparyan, G ;
Vuskovic, K .
COMBINATORICA, 2002, 22 (01) :19-33
[8]  
CONFORTI M, 2001, IN PRESS J COMBIN B
[9]  
CONFORTI M, 1995, LECT NOTES COMPUTER, V920, P321
[10]   COMPOSITIONS FOR PERFECT GRAPHS [J].
CORNUEJOLS, G ;
CUNNINGHAM, WH .
DISCRETE MATHEMATICS, 1985, 55 (03) :245-254
12