G-2003-47
Augmenting Chains in Graphs Without a Skew Star
, et référence BibTeX
The augmenting chain technique has been applied to solve the maximum stable set problem in the class of line graphs (which coincides with the maximum matching problem) and then has been extended to the class of claw-free graphs. In the present paper, we propose a further generalization of this approach. Specifically, we show how to find an augmenting chain in graphs containing no skew star, i.e. a tree with exactly three vertices of degree one of distances 1,2,3 from the only vertex of degree three. As a corollary, we prove that the maximum stable set problem is polynomially solvable in a class that strictly contains claw-free graphs, improving several existing results.
Paru en août 2003 , 21 pages
Axe de recherche
Publication
jan. 2006
Augmenting chains in graphs without a skew star
, et
Journal of Combinatorial Theory, 96(3), 352–366, 2006
référence BibTeX