On the sibling-structure of perfect graphs (Q2277483)

From MaRDI portal
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
    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
    0 references
    0 references
    perfect graph
    0 references
    sibling-structure
    0 references