On conjecture of Berge
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.
- A new property of critical imperfect graphs and some consequences
- Perfect graphs with no \(P_ 5\) and no \(K_ 5\)
- On a conjecture about uniquely colorable perfect graphs
- On essential components and critical sets of a graph
- Elementary bipartite graphs and unique colourability
- On critical edges in minimal imperfect graphs
- On a conjecture of Bourgain
- Incarnations of Berthelot's conjecture
- scientific article; zbMATH DE number 4158667 (Why is no real title available?)
- A simplification of the difficult part of the Berge last conjecture
- scientific article; zbMATH DE number 3902680 (Why is no real title available?)
- scientific article; zbMATH DE number 738898 (Why is no real title available?)
- scientific article; zbMATH DE number 846970 (Why is no real title available?)
- scientific article; zbMATH DE number 867633 (Why is no real title available?)
- scientific article; zbMATH DE number 2192137 (Why is no real title available?)
This page was built for publication: On conjecture of Berge
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804585)
