Abstract
A graph is strongly perfect if every induced subgraph (Formula presented.) of it has a stable set that meets every maximal clique of (Formula presented.). A graph is claw-free if no vertex has three pairwise nonadjacent neighbors. The characterization of claw-free graphs that are strongly perfect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 359-381 |
| Number of pages | 23 |
| Journal | Journal of Graph Theory |
| Volume | 97 |
| Issue number | 3 |
| DOIs | |
| State | Published - Jul 2021 |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
- Discrete Mathematics and Combinatorics
Keywords
- claw-free graphs
- induced subgraphs
- perfect graphs
- strongly perfect graphs