Pairs of disjoint matchings and related classes of graphs

Abstract

For a finite graph $G$, we study the maximum $2$-edge colorable subgraph problem and a related ratio $\frac{\hat{I}¼(G)}{\hat{I}½(G)}$, where $\hat{I}½(G)$ is the matching number of $G$, and $\hat{I}¼(G)$ is the size of the largest matching in any pair $(H,H^{\prime })$ of disjoint matchings maximizing $|H|+|H^{\prime }|$ (equivalently, forming a maximum $2$-edge colorable subgraph). Previously, it was shown that $\frac{4}{5}\le \frac{\hat{I}¼(G)}{\hat{I}½(G)}\le 1$, and the class of graphs achieving $\frac{4}{5}$ was completely characterized. We show here that any rational number between $\frac{4}{5}$ and $1$ can be achieved by a connected graph. Furthermore, we prove that every graph with ratio less than $1$ must admit special subgraphs.