Strongly perfect claw-free graphs—A short proof

Maria Chudnovsky, Cemil Dibek

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish (US)
JournalJournal of Graph Theory
DOIs
StateAccepted/In press - 2021

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • claw-free graphs
  • induced subgraphs
  • perfect graphs
  • strongly perfect graphs

Fingerprint Dive into the research topics of 'Strongly perfect claw-free graphs—A short proof'. Together they form a unique fingerprint.

Cite this