The Library
Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs
Tools
Chudnovsky, Maria, Ries, Bernard and Zwols, Yori (2011) Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs. Discrete Applied Mathematics, Vol.159 (No.17). pp. 1971-1995. doi:10.1016/j.dam.2011.06.024 ISSN 0166-218X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.dam.2011.06.024
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. (C) 2011 Elsevier B.V. All rights reserved.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||
Publisher: | Elsevier Science Ltd. | ||||
ISSN: | 0166-218X | ||||
Official Date: | 2011 | ||||
Dates: |
|
||||
Volume: | Vol.159 | ||||
Number: | No.17 | ||||
Page Range: | pp. 1971-1995 | ||||
DOI: | 10.1016/j.dam.2011.06.024 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |