On a conjecture about uniquely colorable perfect graphs (Q1377674): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Dominating cliques in \(P_ 5\)-free graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3220615 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Star-cutsets and perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3220614 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3220596 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recognizing claw-free perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Normal hypergraphs and the perfect graph conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A characterization of perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On conjecture of Berge / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Perfect zero–one matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Uniquely colorable perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3680855 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coloring graphs with stable cutsets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Topics on perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5184933 / rank | |||
Normal rank |
Latest revision as of 10:30, 28 May 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