Affordable Access

Publisher Website

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.

Statistics

Seen <100 times
0 Comments

More articles like this

β-Perfect Graphs

on Journal of Combinatorial Theor... Jan 01, 1996

A class ofβ-perfect graphs

on Discrete Mathematics Jan 01, 2000

A class ofh-perfect graphs

on Discrete Mathematics Jan 01, 1984
More articles like this..