Perfect graphs (Q2822594)

From the author's introduction: ``Every graph \(G\) clearly satisfies \(\chi(G)\geq\omega(G)\), where \(\omega(G)\) is the clique number of \(G\), because the vertices of a clique must receive different colours. A graph \(G\) is perfect if every induced subgraph \(H\) of \(G\) satisfies \(\chi(H)=\omega(H)\). A chordless cycle of length \(2k+1\), for \(k\geq 2\), satisfies \(3=\chi>\omega=2\), and its complement satisfies \(k+1=\chi>\omega=k\); these graphs are therefore imperfect. Since perfect graphs are closed under taking induced subgraphs, they must be defined by excluding a family \(\mathcal{F}\) of graphs as induced subgraphs. The strong perfect graph theorem (SPGT for short) states that the two examples just given are the only members of \(\mathcal{F}\).'' NEWLINENEWLINENEWLINE Perfect graphs were defined by \textit{C. Berge} [``Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind'', [Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss. Reihe 10, 114--115 (1961)]. This paper presents a survey about perfect graphs that mostly focuses on the SPGT.NEWLINENEWLINEFor the entire collection see [Zbl 1317.05004].