Origins and genesis (Q2758330)

In this first chapter of the book ``Perfect graphs'', the authors trace the origin and evolution of the concept of perfect graphs and the perfect graph conjectures. The origin goes back to Shannon's definition of the zero error capacity of a transmission channel. Section 2 explains how this can be computed as \(C_0(G)=\lim_ {n\rightarrow \infty } \frac{1}{n}\log (\alpha (G)^n)\), where \(G\) is the confounding graph of the message alphabet, \(\alpha \) denotes the stability number of the graph and \(G^n\), the \(n\)th power of the graph \(G\) under the `Cartesian' product. It is shown how \(\log ( \alpha (G))\) is a lower bound and \(\log (\theta (G))\) is an upper bound for \(C_0\), where \(\theta \) is the clique cover number of \(G\). This shows that \(\alpha =\theta \) is a sufficient condition for graphs to satisfy Shannon's requirement that \(C_0(G) = \log (alpha (G))\). One page of Shannon's paper where the capacity is defined is reproduced as Section 4. NEWLINENEWLINENEWLINESection 3 is a reproduction of \textit{C. Berge}'s paper [Discrete Math. 165/166, 61-70 (1997; Zbl 0873.05066)]. Here Berge traces the evolution of the perfect graph conjectures (weak and strong) in detail, giving many personal glimpses. The history of the proofs of perfectness of triangulated graphs and unimodular graphs are mentioned, as also Lovász' weak perfect graph theorem. NEWLINENEWLINENEWLINESection 5, a translation of Berge's 1961 paper in German, deals with Gallai graphs (triangulated graphs) and semi-Gallai graphs (graphs without odd holes). Section 6 is an extract from a 1963 paper of Berge, published by the Indian Statistical Institute where the weak and strong perfect graph conjectures were first explicitly stated.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00015].