Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs

Maria Chudnovsky, Bernard Ries, Yori Zwols

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [14] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.

Original languageEnglish (US)
Pages (from-to)1971-1995
Number of pages25
JournalDiscrete Applied Mathematics
Volume159
Issue number17
DOIs
StatePublished - Oct 28 2011

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Claw-free graphs
  • Forbidden induced subgraphs
  • Strongly perfect graphs
  • Structural graph theory
  • Wireless networking

Fingerprint Dive into the research topics of 'Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs'. Together they form a unique fingerprint.

Cite this