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 Chud-novsky 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 a first substantial answer to the longstanding open question of finding a defining linear system for the stable set polytope of claw-free graphs.
展开▼
