On a conjecture about uniquely colorable perfect graphs (Q1377674)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On a conjecture about uniquely colorable perfect graphs |
scientific article |
Statements
On a conjecture about uniquely colorable perfect graphs (English)
0 references
24 March 1998
0 references
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.
0 references
perfect graph
0 references
uniquely colorable graph
0 references
clique-pair
0 references
claw-free graph
0 references
clique-pair conjecture
0 references