Characterization of saturated graphs related to pairs of disjoint matchings

DOI10.1215/00192082-9719963MaRDI QIDQ2135642zbMATH OpenOpenAlexFDO

Authors Zhengda Mo, Sam Qunell, Anush Tserunyan, Jenna Zomback

Publication date 9 May 2022

Published in Illinois Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.11187, https://projecteuclid.org/journals/illinois-journal-of-mathematics/volume-66/issue-1/Characterization-of-saturated-graphs-related-to-pairs-of-disjoint-matchings/10.1215/00192082-9719963.full

zbMATH Keywords

graph decompositions into even cyclesgraph decompositions into pathsmaximum 2-edge colorable subgraph problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We study the ratio, in a finite graph, of the sizes of the largest matching in any pair of disjoint matchings with the maximum total number of edges and the largest possible matching. Previously, it was shown that this ratio is between 4/5 and 1, and the class of graphs achieving 4/5 was completely characterized. In this paper, we first show that graph decompositions into paths and even cycles provide a new way to study this ratio. We then use this technique to characterize the graphs achieving ratio 1 among all graphs that can be covered by a certain choice of a maximum matching and maximum disjoint matchings.

Recommendations

• Pairs of disjoint matchings and related classes of graphs
• Characterization of a class of graphs related to pairs of disjoint matchings
• A characterization of graphs with given maximum degree and smallest possible matching number. II
• On edge-disjoint pairs of matchings
• On disjoint matchings in cubic graphs

Cites work

• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• scientific article; zbMATH DE number 1947051 (Why is no real title available?)
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• Characterization of a class of graphs related to pairs of disjoint matchings
• Matching theory
• On disjoint matchings in cubic graphs
• On disjoint matchings in cubic graphs: maximum 2-edge-colorable and maximum 3-edge-colorable subgraphs
• On edge-disjoint pairs of matchings
• On maximum \(k\)-edge-colorable subgraphs of bipartite graphs
• On trees with a maximum proper partial 0-1 coloring containing a maximum matching
• Parameterized complexity of \textsc{maximum edge colorable subgraph}
• Paths, Trees, and Flowers
• The Factorization of Linear Graphs
• The NP-Completeness of Edge-Coloring

Cited in

(3)

• Characterization of a class of graphs related to pairs of disjoint matchings
• Pairs of disjoint matchings and related classes of graphs
• Graphs, disjoint matchings and some inequalities

This page was built for publication: Characterization of saturated graphs related to pairs of disjoint matchings

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