论文标题
成对的不交战匹配和相关类别的类别
Pairs of disjoint matchings and related classes of graphs
论文作者
论文摘要
对于有限图$ g $，我们最多研究$ 2 $ - 可着色子图问题和相关比率$ \ frac {μ（g）} {μ（g）} $，其中$ν（g）$是$ g $的匹配数量，$ g $，$μ（g）$是任何对$（$ g）的匹配大小。 + | h'| $（等效地，形成最大$ 2 $ - 边缘可着色子图）。以前，结果表明$ \ frac {4} {5} \ le \ frac {μ（g）} {ν（g）} \ le 1 $，并且成就$ \ frac {4} {5} $的图表已完全表征。我们在这里表明，可以通过连接的图来实现$ \ frac {4} {5} $和$ 1 $之间的任何合理数字。此外，我们证明每个图的比率少于$ 1 $都必须接受特殊的子图。
For a finite graph $G$, we study the maximum $2$-edge colorable subgraph problem and a related ratio $\frac{μ(G)}{ν(G)}$, where $ν(G)$ is the matching number of $G$, and $μ(G)$ is the size of the largest matching in any pair $(H,H')$ of disjoint matchings maximizing $|H| + |H'|$ (equivalently, forming a maximum $2$-edge colorable subgraph). Previously, it was shown that $\frac{4}{5} \le \frac{μ(G)}{ν(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.
