# Wings and perfect graphs

- Authors
- Journal
- Discrete Mathematics 0012-365X
- Publisher
- Elsevier
- Publication Date
- Volume
- 80
- Issue
- 3
- Identifiers
- DOI: 10.1016/0012-365x(90)90248-g

## Abstract

Abstract 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. V. 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.

## There are no comments yet on this publication. Be the first to share your thoughts.