Premium
The Structure of Claw‐Free Perfect Graphs
Author(s) -
Chudnovsky Maria,
Plumettaz Matthieu
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21732
Subject(s) - strong perfect graph theorem , combinatorics , mathematics , chordal graph , indifference graph , cograph , clique sum , claw , split graph , perfect graph , trivially perfect graph , pathwidth , discrete mathematics , bipartite graph , 1 planar graph , line graph , graph , mechanical engineering , engineering
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.