On edge-disjoint pairs of matchings
From MaRDI portal
Publication:998470
DOI10.1016/J.DISC.2007.09.061zbMATH Open1204.05080arXiv0708.1903OpenAlexW2065355983MaRDI QIDQ998470FDOQ998470
Authors: Vahe L. Musoyan, A. V. Tserunyan, Vahan V. Mkrtchyan 
Publication date: 28 January 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Abstract: For a graph G, consider the pairs of edge-disjoint matchings whose union consists of as many edges as possible. Let H be the largest matching among such pairs. Let M be a maximum matching of G. We show that 5/4 is a tight upper bound for |M|/|H|.
Full work available at URL: https://arxiv.org/abs/0708.1903
Recommendations
- Pairs of disjoint matchings and related classes of graphs
- Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs
- scientific article; zbMATH DE number 2104839
- On the number of disjoint perfect matchings of regular graphs with given edge connectivity
- scientific article; zbMATH DE number 1990669
- Neighborhood conditions and edge-disjoint perfect matchings
- Matchings Including or Excluding Certain Edge Sets in Bipartite Graphs
- Characterization of a class of graphs related to pairs of disjoint matchings
- On distance edge-colourings and matchings
- Matching and edge-connectivity in regular graphs
Cites Work
- Matching theory
- On trees with a maximum proper partial 0-1 coloring containing a maximum matching
- Title not available (Why is that?)
- Parallel concepts in graph theory
- On the Core of a Graph†
- Characterization of a class of graphs related to pairs of disjoint matchings
- A note on minimal matching covered graphs
Cited In (11)
- On disjoint matchings in cubic graphs
- Characterization of a class of graphs related to pairs of disjoint matchings
- Pairs of disjoint matchings and related classes of graphs
- Influence of smooth temperature variation on hotspot ignition
- Characterization of saturated graphs related to pairs of disjoint matchings
- On disjoint matchings in cubic graphs: maximum 2-edge-colorable and maximum 3-edge-colorable subgraphs
- On 2-factors with a bounded number of odd components
- Disjoint stable matchings in linear time
- Mixed matchings in graphs
- Title not available (Why is that?)
- Homogeneous charge compression ignition (HCCI) engines: a review
This page was built for publication: On edge-disjoint pairs of matchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q998470)
