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]

Berge C., 1961, Wissenschaftliche Zeitschrift, P114

[2]

CHUDNOVSKY M, IN PRESS ANN MATH

[3] TESTING BALANCEDNESS AND PERFECTION OF LINEAR MATRICES [J].