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.
On the stable set polytope of claw-free graphs
Galluccio A;Gentile C;Ventura P
2008
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
