Almost all Berge Graphs are Perfect
- 1 March 1992
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 1 (1) , 53-79
- https://doi.org/10.1017/s0963548300000079
Abstract
Let Per f(n) denote the set of all perfect graphs on n vertices and let Berge(n) denote the set of all Berge graphs on n vertices. The strong perfect graph conjecture states that Per f(n) = Berge(n) for all n. In this paper we prove that this conjecture is at least asymptotically true, i.e. we show thatKeywords
This publication has 6 references indexed in Scilit:
- Excluding Induced Subgraphs III: A General AsymptoticRandom Structures & Algorithms, 1992
- Excluding induced subgraphs: quadrilateralsRandom Structures & Algorithms, 1991
- K l+1 -Free Graphs: Asymptotic Structure and a 0-1 LawTransactions of the American Mathematical Society, 1987
- Weakly triangulated graphsJournal of Combinatorial Theory, Series B, 1985
- Asymptotic Enumeration of Partial Orders on a Finite SetTransactions of the American Mathematical Society, 1975
- Asymptotic enumeration of partial orders on a finite setTransactions of the American Mathematical Society, 1975