On the stable set polytope of claw-free graphs (Articolo in rivista)

Type
Label
  • On the stable set polytope of claw-free graphs (Articolo in rivista) (literal)
Anno
  • 2008-01-01T00:00:00+01:00 (literal)
Alternative label
  • Galluccio, A.; Gentile, C.; Ventura, P. (2008)
    On the stable set polytope of claw-free graphs
    in Lecture notes in computer science
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Galluccio, A.; Gentile, C.; Ventura, P. (literal)
Pagina inizio
  • 339 (literal)
Pagina fine
  • 350 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 5165 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • COCOA 2008 (literal)
Note
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Autori CNR (literal)
Titolo
  • On the stable set polytope of claw-free graphs (literal)
Abstract
  • We define the class of geared (fuzzy) line graphs as the class of graphs obtained by repeated applications of the extended gear composition to a (fuzzy) line graph H. Using the decomposition theorem for claw-free graphs of Chudnovsky and Seymour, we show that this class represents a large subclass of claw-free graphs having stability number at least 4. We provide a complete linear description of the stable set polytope of geared (fuzzy) line graphs. This result gives the first positive answer to the longstanding open question of finding a defining linear system for the stable set polytope of claw-free graphs. (literal)
Prodotto di
Autore CNR

Incoming links:


Autore CNR di
Prodotto
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
data.CNR.it