Fuzzy antihat graphs are graphs obtained as 2-clique-bond compositions of fuzzy line graphs with three different types of three-cliqued graphs. By the decomposition theorem of Chudnovsky and Seymour [2], fuzzy antihat graphs form a large subclass of claw-free, not quasi-line graphs with stability number at least four and with no 1-joins. A graph is W-perfect if its stable set polytope is described by: nonnegativity, rank, and lifted 5-wheel inequalities. By exploiting the polyhedral properties of the 2-clique-bond composition, we prove that fuzzy antihat graphs are W-perfect and we move a crucial step towards the solution of the longstanding open question of finding an explicit linear description of the stable set polytope of claw-free graphs.
The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are W-perfect
Galluccio A;Gentile C;Ventura P
2014
Abstract
Fuzzy antihat graphs are graphs obtained as 2-clique-bond compositions of fuzzy line graphs with three different types of three-cliqued graphs. By the decomposition theorem of Chudnovsky and Seymour [2], fuzzy antihat graphs form a large subclass of claw-free, not quasi-line graphs with stability number at least four and with no 1-joins. A graph is W-perfect if its stable set polytope is described by: nonnegativity, rank, and lifted 5-wheel inequalities. By exploiting the polyhedral properties of the 2-clique-bond composition, we prove that fuzzy antihat graphs are W-perfect and we move a crucial step towards the solution of the longstanding open question of finding an explicit linear description of the stable set polytope of claw-free graphs.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
