Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids

DOI10.1016/j.dam.2007.05.039zbMath1128.05047OpenAlexW2044531557MaRDI QIDQ2462380

Eugen Mandrescu, Vadim E. Levit

Publication date: 30 November 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.05.039

zbMATH Keywords

triangle-free graphKönig-Egerváry graphgreedoidlocal maximum stable setuniquely restricted maximum matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Critical sets, crowns and local maximum independent sets, Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs, Local maximum stable set greedoids stemming from very well-covered graphs, Forbidden subgraphs and the König-Egerváry property, On maximum matchings in König-Egerváry graphs, On local maximum stable set greedoids, Crowns in bipartite graphs, Graph operations that are good for greedoids, VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS, On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph, The Clique Corona Operation and Greedoids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of the graphs in which the transversal number equals the matching number
• Greedoids
• Matching theory
• The dependence graph for bases in matroids
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
• Alternating cycle-free matchings
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• Generalized subgraph-restricted matchings in graphs
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• A new greedoid: The family of local maximum stable sets of a forest
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• On \(\alpha\)-critical edges in König--Egerváry graphs
• Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
• Introduction to Greedoids
• Vertex packings: Structural properties and algorithms
• Some Matching Problems for Bipartite Graphs
• WELL-COVERED GRAPHS: A SURVEY
• Ranks of zero patterns and sign patterns^*
• Some covering concepts in graphs
• On the jump number problem in hereditary classes of bipartite graphs
• Uniquely restricted matchings