Characterization Of A Class Of Graphs Related To Pairs Of Disjoint Matchings

Abstract

For a given graph consider a pair of disjoint matchings the union of which contains as many edges as possible. Furthermore, consider the relation of the cardinalities of a maximum matching and the largest matching in those pairs. It is known that this relation does not exceed 5/4 for any graph. We characterize the class of graphs for which this relation is precisely 5/4. Our characterization implies that these graphs contain a spanning subgraph, every component of which is the minimal graph of this class.

arXiv comment33 pages, 10 figures

References in corpus (5)

• On trees with a maximum proper partial 0-1 coloring containing a maximum matching
• On complexity of special maximum matchings constructing
• A note on minimal matching covered graphs
• On Edge-Disjoint Pairs Of Matchings
• Two polynomial algorithms for special maximum matching constructing in trees

Cited by in corpus (5)

• On disjoint matchings in cubic graphs
• On disjoint matchings in cubic graphs: maximum 2- and 3-edge-colorable subgraphs
• On Edge-Disjoint Pairs Of Matchings
• Pairs of disjoint matchings and related classes of graphs
• On a constructive characterization of a class of trees related to pairs of disjoint matchings