Abstract:An edge cut C of a graph G is tight if |C \M| = 1 for every perfect matching M of G. Barrier-cuts and 2-separation cuts, also referred to as ELP-cuts, are two important types of tight cuts in matching covered graphs. Edmonds, Lovasz and Pulleyblank [Brick decompositions and the matching rank of graphs, Combinatorica 2(3) (1982) 247-274] proved that if a matching covered graph has a non-trivial tight cut, then it also has a non-trivial ELP-cut. In confirmation of a conjecture proposed by Carvalho, Lucchesi and Murty, Chen et. al. [Laminar tight cuts in matching covered graphs, J. Comb. Theory, Ser. B, 150 (2021) 177-194] showed that if C is a non-trivial tight cut of a matching covered graph G, then G has at least one C-sheltered non-trivial barrier or a 2-separation cut that is laminar with C.
In this paper, we present a complete characterization of non-trivial tight cuts in matching covered graphs, from which the result of Chen et. al. can be derived directly. Moreover, we show that the lower bound of the number of C-sheltered non-trivial barrier or a 2-separation cut that is laminar with C in the result of Chen et. al. is sharp.
| Subjects: | Combinatorics (math.CO) |
| Cite as: | arXiv:2605.25695 [math.CO] |
| (or arXiv:2605.25695v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25695 arXiv-issued DOI via DataCite (pending registration) |
From: Fuliang Lu [view email]
[v1]
Mon, 25 May 2026 10:53:27 UTC (2,640 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。