Perfect graphs

Publication date 30 September 2016

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

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].

Recommendations

Cited in

(29)

This page was built for publication: Perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2822594)