Recognizing Berge graphs

被引：175
作者：
Chudnovsky, M
Cornuéjols, G
Liu, XM
Seymour, P
Vuskovic, K
机构：
[1] Princeton Univ, Dept Math, Princeton, NJ 08544 USA
[2] Carnegie Mellon Univ, Tepper Sch Business, Pittsburgh, PA 15213 USA
[3] Fac Sci Luminy, Lab Informat Fondamentale, F-13288 Marseille, France
来源：
COMBINATORICA | 2005年 / 25卷 / 02期
关键词：
D O I：
10.1007/s00493-005-0012-8
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A graph is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one. In this paper we give an algorithm to test if a graph G is Berge, with running time O(vertical bar V(G)vertical bar(9)). This is independent of the recent proof of the strong perfect graph conjecture.
引用
收藏
页码：143 / 186
页数：44
相关论文
共 9 条
1