The structure of claw-free perfect graphs

Maria Chudnovsky, Matthieu Plumettaz

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

In 1988, Chvátal and Sbihi (J Combin Theory Ser B 44(2) (1988), 154-176) proved a decomposition theorem for claw-free perfect graphs. They showed that claw-free perfect graphs either have a clique-cutset or come from two basic classes of graphs called elementary and peculiar graphs. In 1999, Maffray and Reed (J Combin Theory Ser B 75(1) (1999), 134-156) successfully described how elementary graphs can be built using line-graphs of bipartite graphs using local augmentation. However, gluing two claw-free perfect graphs on a clique does not necessarily produce claw-free graphs. In this article, we give a complete structural description of claw-free perfect graphs. We also give a construction for all perfect circular interval graphs.

Original languageEnglish (US)
Pages (from-to)203-230
Number of pages28
JournalJournal of Graph Theory
Volume75
Issue number3
DOIs
StatePublished - Mar 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • claw-free
  • graph structure
  • perfect
  • quasi-line graph
  • trigraph

Fingerprint

Dive into the research topics of 'The structure of claw-free perfect graphs'. Together they form a unique fingerprint.

Cite this