Recognizing Berge graphs
Recognizing Berge graphs
复制标题
DOI：
10.1007/s00493-005-0012-8
复制
发表时间：
2005-01-01
期刊：
影响因子：
1.1
通讯作者：
Vuskovic, K
中科院分区：
文献类型：
--
作者：
Chudnovsky, M;Cornuéjols, G;Vuskovic, K
一个图是Berge图，如果G的导出子图都不是长度至少为5或1的补数的奇圈。本文给出了一个判定图G是否Berge的算法，其运行时间为O（竖线V（G）竖线（9））。这是独立的最近证明的强完美图猜想。
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.