Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. A note on tight cuts ...
Article

A note on tight cuts in matching-covered graphs

Xiao Zhao, Sheng Chen
Download article
Open on arXiv
Submitted on
January 8, 2020
Accepted on
May 28, 2021
Published on
June 14, 2021
Last modified on
March 31, 2025
Volume 23
vol. 23:1
Graph Theory
DOI
10.46298/dmtcs.6013
License
arXiv.org - Non-exclusive license to distribute
Indicators
919
Views
662
Downloads

A note on tight cuts in matching-covered graphs

Xiao Zhao, Sheng Chen
Abstract
Edmonds, Lov\'asz, 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$. Comment: 7pages
Keywords
  • Mathematics - Combinatorics
Mathematics Subject Classification 2020
  • 05C70 - Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Preview
Loading PDF preview...