On critical edges in minimal imperfect graphs (Q1924138)

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.