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

DOI10.1016/J.DAM.2007.05.039zbMATH Open1128.05047OpenAlexW2044531557MaRDI QIDQ2462380FDOQ2462380

Authors: Vadim E. Levit, Eugen Mandrescu 

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

Recommendations

• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• Uniquely restricted matchings
• Graphs in which some and every maximum matching is uniquely restricted
• Local maximum stable set greedoids stemming from very well-covered graphs
• Very well-covered graphs of girth at least four and local maximum stable set greedoids

zbMATH Keywords

triangle-free graphgreedoidlocal maximum stable setuniquely restricted maximum matchingKönig-Egerváry graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• Forbidden subgraphs and the König-Egerváry property
• On duality between local maximum stable sets of a graph and its line-graph
• The Clique Corona Operation and Greedoids
• Graphs in which some and every maximum matching is uniquely restricted
• On local maximum stable set greedoids
• Critical sets, crowns and local maximum independent sets
• Graph operations that are good for greedoids
• Local maximum stable set greedoids stemming from very well-covered graphs
• On maximum matchings in König-Egerváry graphs
• Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs
• Very well-covered graphs of girth at least four and local maximum stable set greedoids
• Crowns in bipartite graphs

This page was built for publication: Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids

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