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|.
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
- scientific article; zbMATH DE number 854567 (Why is no real title available?)
- A note on minimal matching covered graphs
- Characterization of a class of graphs related to pairs of disjoint matchings
- Matching theory
- On the Core of a Graph†
- On trees with a maximum proper partial 0-1 coloring containing a maximum matching
- Parallel concepts in graph theory
Cited in
(11)- On disjoint matchings in cubic graphs
- Characterization of a class of graphs related to pairs of disjoint matchings
- Influence of smooth temperature variation on hotspot ignition
- Pairs of disjoint matchings and related classes of graphs
- 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
- scientific article; zbMATH DE number 1990669 (Why is no real title available?)
- 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)
