论文标题
在匹配覆盖的图中紧密切割的注释
A note on tight cuts in matching-covered graphs
论文作者
论文摘要
Edmonds，Lovász和Pulleyblank表明，如果匹配的覆盖图具有非平凡的紧身切割，那么它也具有非平凡的ELP切割。 Carvalho等。给出了更强的猜想：如果匹配的覆盖图具有非平凡的紧身$ C $，那么它还具有非平凡的ELP切割，不会超过$ c $。 Chen等人给出了猜想的证明。此注释灵感来自Carvalho等人的论文。我们给出了简化的猜想证明，并证明了以下结果比猜想要强一些：如果非平凡的紧密切割$ c $的匹配图形$ g $不是ELP切割，则有一个序列$ g_1 = g_1 = g，g_2，g_2，\ ldots，\ ldots，g_r，g_r，g_r，r \ e \ geq2 $ for Matching of Groups $ -1，例如，c，例如，c，例如，y-ld，r f \ l f \ ld，r f \ l f。 $ g_i $具有elp-cut $ c_i $，$ g_ {i+1} $是$ c_i $ -g_i $的$ c_i $ - co $，$ c $是$ 2 $ - 分类削减$ g_r $。
Edmonds, Lovász, and Pulleyblank showed that if a matching covered graph has a nontrivial tight cut, then it also has a nontrivial ELP-cut. Carvalho et al. gave a stronger conjecture: if a matching covered graph has a nontrivial tight cut $C$, then it also has a nontrivial ELP-cut that does not cross $C$. Chen, et al gave a proof of the conjecture. This note is inspired by the paper of Carvalho et al. We give a simplified proof of the conjecture, and prove the following result which is slightly stronger than the conjecture: if a nontrivial tight cut $C$ of a matching covered graph $G$ is not an ELP-cut, then there is a sequence $G_1=G, G_2,\ldots,G_r, r\geq2$ of matching covered graphs, such that for $i=1, 2,\ldots, r-1$, $G_i$ has an ELP-cut $C_i$, and $G_{i+1}$ is a $C_i$-contraction of $G_i$, and $C$ is a $2$-separation cut of $G_r$.
