Wings and perfect graphs (Q1112849): Difference between revisions

An edge uv of a graph G is called a wing if there exists a chordless path with vertices u, v, x, y and edges uv, vx, xy. The wing-graph W(G) of a graph G is a graph having the same vertex set as G; uv is an edge in W(G) if and only if uv is a wing in G. A graph G is saturated if G is isomorphic to W(G). A star-cutset in a graph G is a non-empty set of vertices such that G-C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. Vašek Chvátal proposed to call a graph unbreakable if neither G nor its complement contain a star- cutset. We establish several properties of unbreakable graphs using the notions of wings and saturation. In particular, we obtain seven equivalent versions of the Strong perfect graph conjecture.