On (P5, diamond)-free graphs

被引：20

作者：

Arbib, C ^{[1
]}

Mosca, R ^{[1
]}

机构：

[1] Univ Aquila, Dipartimento Matemat Pura & Applicata, I-67010 Coppito, Laquila, Italy

来源：

DISCRETE MATHEMATICS | 2002年 / 250卷 / 1-3期

关键词：

stability number; chromatic number; clique covers; P-5-free graphs;

D O I：

10.1016/S0012-365X(01)00268-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We study the stability number, chromatic number and clique cover of graphs with no induced P, and diamonds. In particular, we provide a way to obtain all imperfect (P-5, diamond)-free graphs by iterated point multiplication or substitution from a finite collection of small basic graphs. Corollaries of this and other structural properties. among which a result of Bacso and Tuza, are (i) combinatorial algorithms to solve coloring, clique cover and stable set in the class of (P-5, diamond)-free graphs, (ii) a complete description of the stable set polytope of (P-5, diamond)-free graphs, and (iii) the existence of non-trivial h-perfect graphs which are not t-perfect. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：1 / 22

页数：22

共 22 条

[1] [Anonymous], 2001, GRAPH THEORY
[2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[3] Arbib C, 1999, J COMBIN MATH COMPUT, V30, P3
[4] Bacso G., 1990, PERIOD MATH HUNG, V21, P303, DOI DOI 10.1007/BF02352694
[5] GRAPHS WITH NO INDUCED C-4 AND 2K2
BLAZSIK, Z
HUJTER, M
PLUHAR, A
TUZA, Z
[J]. DISCRETE MATHEMATICS, 1993, 115 (1-3) : 51 - 55
[6] Polyhedral characterizations and perfection of line graphs
Cao, DS
Nemhauser, GL
[J]. DISCRETE APPLIED MATHEMATICS, 1998, 81 (1-3) : 141 - 154
[7] 4 CLASSES OF PERFECTLY ORDERABLE GRAPHS
CHVATAL, V
HOANG, CT
MAHADEV, NVR
DEWERRA, D
[J]. JOURNAL OF GRAPH THEORY, 1987, 11 (04) : 481 - 495
[8] STABILITY NUMBER OF BULL-FREE AND CHAIR-FREE GRAPHS
DESIMONE, C
SASSANO, A
[J]. DISCRETE APPLIED MATHEMATICS, 1993, 41 (02) : 121 - 129
[9] ON GRAPHS WITHOUT P-5 AND (P-5)OVER-BAR
FOUQUET, JL
GIAKOUMAKIS, V
MAIRE, F
THUILLIER, H
[J]. DISCRETE MATHEMATICS, 1995, 146 (1-3) : 33 - 44
[10] The rank facets of the stable set polytope for claw-free graphs
Galluccio, A
Sassano, A
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 69 (01) : 1 - 38

← 1 2 3 →