RECOGNIZING BULL-FREE PERFECT GRAPHS

被引：26

作者：

REED, B

SBIHI, N

机构：

[1] UNIV WATERLOO,DEPT COMBINATOR & OPTIMIZAT,WATERLOO,ON N2L 3G1,CANADA

[2] CTR NATL COORDINAT & PLANIFICAT RECH SCI & TECH,RABAT,MOROCCO

来源：

GRAPHS AND COMBINATORICS | 1995年 / 11卷 / 02期

关键词：

D O I：

10.1007/BF01929485

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A bull is the graph obtained from a triangle by adding two pendant vertices adjacent to distinct vertices of the triangle. Chvatal and Sbihi showed that the strong perfect graph conjecture holds for Bull-free graphs. We give a polynomial time recognition algorithm for Bull-free perfect graphs.

引用

页码：171 / 178

页数：8

共 12 条

[1]

BERGE C, 1984, TOPICS PERFECT GRAPH, pR11

[2]

Berge C., 1961, FARBUNG GRAPHEN DERE, P114

[3]

BURLET M, 1984, TOPICS PERFECT GRAPH, pR11

[4] STAR-CUTSETS AND PERFECT GRAPHS [J].