On Critical Edges in Minimal Imperfect Graphs

An edge of a graph is calledcritical, if deleting it the stability number of the graph increases, and a nonedge is calledco-critical, if adding it to the graph the size of the maximum clique increases. We prove in this paper, 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 thestrong perfect graph conjectureand prove its validity for some particular cases. Among the consequences we prove that the existence in every minimal imperfect graphGof a maximum cliqueQ, for whichG−Qhas one unique optimal coloration, is equivalent to the strong perfect graph conjecture, as well as the existence of a vertexvinV(G) such that the (uniquely colorable) perfect graphG−vhas a “combinatorially forced” color class. These statements contain earlier results involving more critical edges, of Markossian, Gasparian and Markossian, and those of Bacsó and they also imply that a class of partitionable graphs constructed by Chvátal, Graham, Perold, and Whitesides does not contain counterexamples to the strong perfect graph conjecture.