Strongly perfect claw‐free graphs—A short proof
Abstract
A graph is strongly perfect if every induced subgraph of it has a stable set that meets every maximal clique of . 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jan 11, 2021
- Source ID
- 10.1002/jgt.22659
Entities
People
- Cemil Dibek
- Maria Chudnovsky
Organizations
- Army Research Office
- National Science Foundation Division of Mathematical Sciences
- Princeton University
- United States Army Research Laboratory