On the sibling-structure of perfect graphs (Q2277483): Difference between revisions
From MaRDI portal
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