On conjecture of Berge (Q804585)

A new approach to the strong perfect graph conjecture based on the concepts of critical edge and critical component is investigated. An edge \(e\in E\) of a graph \(G=(V,E)\) is called critical if \(\alpha (G)<\alpha (G-e)\), where \(\alpha\) (*) is the stability number and G-e is the spanning subgraph of G obtained by deleting the edge e. The maximal induced subgraph of G each pair of vertices of which are connected by a path consisting of critical edges is called a critical subgraph. The obtained result is the following: if a critical imperfect graph (p-graph) G and its complement both contain incomplete critical components then G is an odd hole or the complement of it. As consequence, three new conjectures, each of them being equivalent to the strong perfect graphs conjecture, are formulated.