Combinatorics and algorithms for augmenting graphs

DOI10.1007/s00373-015-1660-0zbMath1342.05098arXiv1410.8774OpenAlexW1869170457WikidataQ59474941 ScholiaQ59474941MaRDI QIDQ2631076

Vadim V. Lozin, Konrad K. Dabrowski, Dominique de Werra, Victor Zamaraev

Publication date: 28 July 2016

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.8774

zbMATH Keywords

independent setpolynomial-time algorithmaugmenting graphgraph class

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Generalized Ramsey theory (05C55) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

New results on independent sets in extensions of \(2K_2\)-free graphs

Cites Work

• Unnamed Item
• On finding augmenting graphs
• Some results on graphs without long induced paths
• 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é
• Stable sets in certain \(P_6\)-free graphs
• New results on maximum induced matchings in bipartite graphs and beyond
• New sufficient conditions for \(\alpha\)-redundant vertices
• Augmenting chains in graphs without a skew star.
• TWO THEOREMS IN GRAPH THEORY
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Paths, Trees, and Flowers