On the sibling-structure of perfect graphs (Q2277483): Difference between revisions

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.