On conjecture of Berge
type: Item
instance of: scholarly article
title: On conjecture of Berge
zbMATH Open document ID: 0728.05029
DOI: 10.1016/0095-8956(92)90010-U
author: N. E. Zubov
published in: Journal of Combinatorial Theory. Series B
publication date: 1992-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 4202286
zbMATH Keywords: strong perfect graph conjecture
zbMATH Keywords: critical edge
zbMATH Keywords: critical component
zbMATH Keywords: critical subgraph
zbMATH Keywords: critical imperfect graph
MaRDI profile type: Publication
Recommended article: Q3487429
Recommended article: On a conjecture of W. Bergweiler
Recommended article: On conjectures of Berge and Chvátal
Recommended article: On a conjecture of Bourgain
Recommended article: On a conjecture of Bergstra and Tucker
Recommended article: Q5117584
Recommended article: Q3137321
Recommended article: Q3480091
Recommended article: On the Berry conjecture
description: scientific article; zbMATH DE number 4202286