On the sibling-structure of perfect graphs (Q2277483): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / cites work | |||
Property / cites work: Q3222224 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the \(P_ 4\)-structure of perfect graphs. III: Partner decompositions / 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 new property of critical imperfect graphs and some consequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A semi-strong perfect graph theorem / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0095-8956(90)90031-t / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1981268562 / rank | |||
Normal rank |
Latest revision as of 11:21, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the sibling-structure of perfect graphs |
scientific article |
Statements
On the sibling-structure of perfect graphs (English)
0 references
1990
0 references
Let x,y be two vertices of a graph G. The author calls x and y sibilings with respect to a set Q if both \(Q\cup \{x\}\) and \(Q\cup \{y\}\) induce a \(P_ 4\) (the chordless path on four vertices). Let us say that \(G=(V,E)\) and \(G'=(V',E')\) have the same sibling-structure if there is a bijection f: \(V\to V'\) such that x and y are siblings with respect to Q in G if and only if f(x) and f(y) are siblings with respect to f(Q) in \(G'\). A graph G is perfect if for each induced subgraph H of G, the chromatic number of H equals the order of a largest clique in H. The author shows that if G and \(G'\) have the same sibling-structure then either both G and \(G'\) are perfect or both G and \(G'\) are imperfect.
0 references
perfect graph
0 references
sibling-structure
0 references