The Structure of Claw‐Free Perfect Graphs | Zendy

Chudnovsky Maria | Zendy; Plumettaz Matthieu | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research