On the stability number of claw-free P5-free and more general graphs

被引：17

作者：

Brandstädt, A

Hammer, PL

机构：

[1] Univ Rostock, Fachbereich Informat, D-18051 Rostock, Germany

[2] Rutgers State Univ, RUTCOR, New Brunswick, NJ 08903 USA

来源：

DISCRETE APPLIED MATHEMATICS | 1999年 / 95卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

stability number; independence number; claw-free graphs; simplicial vertices; polynomial-time algorithm;

D O I：

10.1016/S0166-218X(99)00072-4

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this note we show that the stability number of a (4-pan, chair, K-1,K-4,P-5)-free graph which has no simplicial vertex is bounded by 3. This generalizes the case of (claw, P-5)-free graphs and leads to a very simple polynomial-time algorithm for determining the stability number of (claw, Ps)-free graphs and, more generally, of (4-pan,chair, K-1,K-4, P-5)-free graphs. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：163 / 167

页数：5

共 7 条

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