Characterization of saturated graphs related to pairs of disjoint matchings

DOI10.1215/00192082-9719963zbMATH Open1487.05211arXiv2011.11187OpenAlexW3106856487MaRDI QIDQ2135642FDOQ2135642

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)

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.

Full work available at URL: https://arxiv.org/abs/2011.11187

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

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)

Cites Work

• Matching theory
• Paths, Trees, and Flowers
• The Factorization of Linear Graphs
• On trees with a maximum proper partial 0-1 coloring containing a maximum matching
• Title not available (Why is that?)
• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• 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
• Characterization of a class of graphs related to pairs of disjoint matchings
• On maximum \(k\)-edge-colorable subgraphs of bipartite graphs
• Parameterized complexity of \textsc{maximum edge colorable subgraph}

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)