On critical edges in minimal imperfect graphs
type: Item
instance of: scholarly article
title: On critical edges in minimal imperfect graphs
zbMATH Open document ID: 0855.05062
author: András Sebö
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-01-26T00:00:00Z
review text: An edge of a graph is called critical, if deleting it the stability number of the graph increases, and a nonedge is called co-critical, if adding it to the graph the size of the maximum clique increases. We prove that the minimal imperfect graphs containing certain configurations of two critical edges and one co-critical nonedge are exactly the odd holes or antiholes. Then we deduce some reformulations of the strong perfect graph conjecture and prove its validity for some particular cases. Among the consequences we prove that the existence in every minimal imperfect graph \(G\) of a maximum clique \(Q\), for which \(G-Q\) has one unique optimal coloration, is equivalent to the strong perfect graph conjecture, as well as the existence of a vertex \(v\) in \(V(G)\) such that the (uniquely colorable) perfect graph \(G- v\) has a ``combinatorially forced'' color class. These statements contain earlier results involving more critical edges, of \textit{S. E. Markossian}, \textit{G. S. Gasparian} and \textit{A. S. Markossian} [J. Comb. Theory, Ser. B 56, No. 1, 97-107 (1992; Zbl 0758.05029)] and those of \textit{G. Bacsó} [\(\alpha\)-critical edges in perfect graphs (manuscript 1989)] and they also imply that a class of partitionable graphs constructed by \textit{V. Chvátal}, \textit{R. L. Graham}, \textit{A. F. Perold} and \textit{S. H. Whitesides} [Perfect graphs, Ann. Discrete Math. 21, 197-206 (1984; Zbl 0556.05012)] does not contain counterexamples to the strong perfect graph conjecture.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 934805
zbMATH Keywords: stability number
zbMATH Keywords: maximum clique
zbMATH Keywords: minimal imperfect graphs
zbMATH Keywords: strong perfect graph conjecture
zbMATH Keywords: critical edges
MaRDI profile type: Publication
full work available at URL: jctb.1996.0034
OpenAlex ID: W2155450181
DOI: 10.1006/JCTB.1996.0034
description: scientific article; zbMATH DE number 934805