IGL Spring 2020: Pairs of disjoint matchings
From Philipp Hieronymi
views
comments
From Philipp Hieronymi
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.
A trivial tight upper bound for this ratio is 1, and in earlier work, A. Tserunyan showed that 4/5 is a tight lower bound and characterized the graphs that achieve 4/5. We have found that all rational numbers between 4/5 and 1 can be realized as the ratio of a connected graph and discovered a class of subgraphs that appear in every graph with ratio less than 1. We have also fully characterized all graphs with ratio less than 1 that are covered by a specific choice of matchings. This is very close to our ultimate goal of characterizing all graphs with ratio 1.