On a conjecture about uniquely colorable perfect graphs (Q1377674): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Created claim: Wikidata QID (P12): Q123314134, #quickstatements; #temporary_batch_1707216511891 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q123314134 / rank | |||
Normal rank |
Revision as of 13:39, 6 February 2024
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