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 language | English (US) |
|---|---|
| Pages (from-to) | 203-230 |
| Number of pages | 28 |
| Journal | Journal of Graph Theory |
| Volume | 75 |
| Issue number | 3 |
| DOIs | |
| State | Published - Mar 2014 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
Keywords
- claw-free
- graph structure
- perfect
- quasi-line graph
- trigraph