Journal of Combinatorics
Volume 9 (2018)
On tight cuts in matching covered graphs
Pages: 163 – 184
Barrier cuts and 2-separation cuts are two familiar types of tight cuts in matching covered graphs. See Lovász (, 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 (, 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 (, 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 nontrivial 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.
perfect matchings, matching covered graphs, tight cuts
2010 Mathematics Subject Classification
Received 18 November 2014
Published 5 January 2018