The Structure of Claw‐Free Perfect Graphs
Maria Chudnovsky, Matthieu Plumettaz · Journal of Graph Theory · 2013
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.