On a conjecture about uniquely colorable perfect graphs (Q1377674): Difference between revisions

In a graph \(G\) with maximum clique size \(\omega \), a clique-pair means two cliques of size \(\omega \) whose intersection has size \(\omega -1\). The subject of this paper is the so-called clique-pair conjecture (CPC) which states that if a uniquely colorable perfect graph is not a clique then it contains a clique-pair. The deepest result, in connection with the CPC, was obtained by \textit{J. Fonlupt} and \textit{A. Zemirline} [IMAG Rapp. Technique RT-16, Fev. 1987]: the CPC is true for graphs \(G\) with \(\omega (G)\leq 3\). In this paper the structure of the possible counterexamples to this conjecture is studied, and, combining the author's result with those in \textit{J. Fonlupt} and \textit{A. Zemirline} (1987), a new proof of the CPC for 3-chromatic graphs is obtained; the validity of the CPC for claw-free graphs is also proved.