Polytope des independants d'un graphe serie-parallele

AbstractA graph is said to be serie-parallel if it doesn't contain an homeomorph to K4. The aim of the paper is the demonstration of Chvatal's conjecture on the polytope of independent set of vertices in such graphs. This is done classically by using LP-duality, the algorithm for constructing the primal-dual solution having the nice property to be linear in the number of vertices