Strongly perfect claw-free graphs—A short proof

Maria Chudnovsky, Cemil Dibek

Research output: Contribution to journalArticlepeer-review

3 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)
Pages (from-to)359-381
Number of pages23
JournalJournal of Graph Theory
Volume97
Issue number3
DOIs
StatePublished - 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

Fingerprint

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

Cite this