Augmenting chains in graphs without a skew star.

DOI10.1016/j.jctb.2005.09.007zbMath1089.05067OpenAlexW2128954556MaRDI QIDQ2490836

Michael U. Gerber, Alain Hertz, Vadim V. Lozin

Publication date: 18 May 2006

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2005.09.007

zbMATH Keywords

stable setpolynomial algorithmclaw-free graphsline graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Combinatorics and algorithms for augmenting graphs ⋮ From matchings to independent sets ⋮ On finding augmenting graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs

Cites Work

• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Matching theory
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Stability number of bull- and chair-free graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Bipartite graphs without a skew star
• Polynomially solvable cases for the maximum stable set problem
• TWO THEOREMS IN GRAPH THEORY
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Paths, Trees, and Flowers

This page was built for publication: Augmenting chains in graphs without a skew star.