The Structure of Claw-Free Perfect Graphs

In 1988, Chvátal and Sbihi [4] 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 [6] 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 paper we give a complete structural description of claw-free perfect graphs. We also give a construction for all perfect circular interval graphs