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.
- A characterization of perfect graphs
- No antitwins in minimal imperfect graphs
- Normal hypergraphs and the perfect graph conjecture
- On a property of the class of n-colorable graphs
- On Minimal Blocks
- Perfect zero–one matrices
- Star-cutsets and perfect graphs
- The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
This page was built for publication: Wings and perfect graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1112849)
