On (P5, diamond)-free graphs

被引：21

作者：

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 [J].

BLAZSIK, Z ;

HUJTER, M ;

PLUHAR, A ;

TUZA, Z .

DISCRETE MATHEMATICS, 1993, 115 (1-3) :51-55

[6] Polyhedral characterizations and perfection of line graphs [J].

Cao, DS ;

Nemhauser, GL .

DISCRETE APPLIED MATHEMATICS, 1998, 81 (1-3) :141-154

[7] 4 CLASSES OF PERFECTLY ORDERABLE GRAPHS [J].

CHVATAL, V ;

HOANG, CT ;

MAHADEV, NVR ;

DEWERRA, D .

JOURNAL OF GRAPH THEORY, 1987, 11 (04) :481-495

[8] STABILITY NUMBER OF BULL-FREE AND CHAIR-FREE GRAPHS [J].

DESIMONE, C ;

SASSANO, A .

DISCRETE APPLIED MATHEMATICS, 1993, 41 (02) :121-129

[9] ON GRAPHS WITHOUT P-5 AND (P-5)OVER-BAR [J].

FOUQUET, JL ;

GIAKOUMAKIS, V ;

MAIRE, F ;

THUILLIER, H .

DISCRETE MATHEMATICS, 1995, 146 (1-3) :33-44

[10] The rank facets of the stable set polytope for claw-free graphs [J].

Galluccio, A ;

Sassano, A .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1997, 69 (01) :1-38

← 1 2 3 →