Augmenting chains in graphs without a skew star.

DOI10.1016/J.JCTB.2005.09.007MaRDI QIDQ2490836zbMATH OpenOpenAlexFDO

Authors Michael U. Gerber, Alain Hertz, Vadim 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

claw-free graphsline graphspolynomial algorithmstable set

Mathematics Subject Classification ID

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

Recommendations

• Finding augmenting chains in extensions of claw-free graphs
• On finding augmenting graphs
• Augmenting graphs for independent sets
• scientific article; zbMATH DE number 7651209
• Combinatorics and algorithms for augmenting graphs
• An extension of the star complement technique for regular graphs
• scientific article; zbMATH DE number 1759470
• Augmenting the algebraic connectivity for certain families of graphs
• Edge-connectivity augmentations of~graphs~and~hypergraphs
• Increasing the connectivity of the star graphs

Cites work

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

Cited in

(6)

• Finding augmenting chains in extensions of claw-free graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• From matchings to independent sets
• Combinatorics and algorithms for augmenting graphs
• Independent set reconfiguration in H-free graphs
• On finding augmenting graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2490836)