Journal of Combinatorics

Volume 9 (2018)

Number 1

On tight cuts in matching covered graphs

Pages: 163 – 184

DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n1.a8

Authors

Marcelo H. Carvalho (Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Campo Grande, MS, Brazil)

Cláudio L. Lucchesi (Faculdade de Computação, Universidade Federal de Mato Grosso do Sul, Campo Grande, MS, Brazil)

U. S. R. Murty (Department of Mathematics, University of Waterloo, Ontario, Canada)

Abstract

Barrier cuts and 2-separation cuts are two familiar types of tight cuts in matching covered graphs. See Lovász ([7], 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 ([6], 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 ([9], 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.

Keywords

perfect matchings, matching covered graphs, tight cuts

2010 Mathematics Subject Classification

05C70

Received 18 November 2014

Published 5 January 2018