On tight cuts in matching covered graphs
On tight cuts in matching covered graphs
复制标题
DOI：
10.4310/joc.2018.v9.n1.a8
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
M. H. Carvalho;C. Lucchesi;U. Murty
中科院分区：
文献类型：
--
作者：
M. H. Carvalho;C. Lucchesi;U. Murty
在匹配覆盖图中，屏障切割和2-分离切割是两种常见的紧密切割类型，参见Lovász（[6], 1987）。我们将这两种类型的紧切称为elp切。Edmonds， Lovász和Pulleyblank（[5], 1982）给出了匹配理论的一个基本结果，即如果匹配覆盖图具有非平凡的紧切，那么它也具有非平凡的elp切。他们对这个结果的证明是基于线性规划技术的。Szigeti（[8], 2002）给出了一个更简单的纯图理论证明。这篇笔记的灵感来自Szigeti的论文。利用匹配图中的势垒性质，我们称之为Dulmage-Mendelsohn势垒，给出了Edmonds-Lovász-Pulleyblank （ELP）定理的另一种证明。我们推测，给定匹配覆盖图中非elp -切的任何紧切C，在该图中存在一个不与C相交的非平凡elp -切D。这里我们给出了对双临界图和最多两个砖块匹配覆盖图的有效性的简短证明。
Barrier cuts and 2-separation cuts are two familiar types of tight cuts in matching covered graphs, see Lovász ([6], 1987). We refer to these two types of tight cuts as ELP-cuts. A fundamental result of matching theory, due to Edmonds, Lovász, and Pulleyblank ([5], 1982) states that if a matching covered graph has a nontrivial tight cut, then it also has a nontrivial ELP-cut. Their proof of this result was based on linear programming techniques. An easier and purely graph theoretical proof was given by Szigeti ([8], 2002). This note is inspired by Szigeti’s paper. Using properties of barriers in matchable graphs, which we call Dulmage-Mendelsohn barriers, we give an alternative proof of the Edmonds-Lovász-Pulleyblank (ELP) Theorem. We conjecture that, given any tight cut C in a matching covered graph that is not an ELP-cut, there exists a nontrivial ELP-cut D in that graph which does not cross C. Here we give a short proof of the validity of this conjecture for bicritical graphs and also for matching covered graphs with at most two bricks.