• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Claw-Free Graphs With Strongly Perfect Complements. Fractional and Integral Version. Part II. Nontrivial strip-structures

Thumbnail
Date
2011
Dewey
Principes généraux des mathématiques
Sujet
Structural graph theory; Wireless networking; Stronglyperfectgraphs; Forbidden induced subgraphs; Claw-freegraphs
Journal issue
Discrete Applied Mathematics
Volume
159
Number
17
Publication date
2011
Article pages
1996-2029
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.dam.2011.06.031
URI
https://basepub.dauphine.fr/handle/123456789/9279
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Zwols, Yori
Ries, Bernard
Chudnovsky, Maria
Type
Article accepté pour publication ou publié
Abstract (EN)
Stronglyperfectgraphs have been studied by several authors (e.g., Berge and Duchet (1984) [1], Ravindra (1984) [7] and Wang (2006) [8]). In a series of two papers, the current paper being the second one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-freegraphs that are fractionally stronglyperfect 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-freegraphs that are fractionally stronglyperfect 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) [8] gave a characterization of stronglyperfectclaw-freegraphs. As a corollary of the results in this paper, we obtain a characterization of claw-freegraphs whose complements are stronglyperfect.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.