Xiao Zhao ; Sheng Chen - A note on tight cuts in matching-covered graphs

dmtcs:6013 - Discrete Mathematics & Theoretical Computer Science, June 14, 2021, vol. 23 no. 1 - https://doi.org/10.46298/dmtcs.6013
A note on tight cuts in matching-covered graphsArticle

Authors: Xiao Zhao ; Sheng Chen

    Edmonds, Lovász, 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$.


    Volume: vol. 23 no. 1
    Section: Graph Theory
    Published on: June 14, 2021
    Accepted on: May 28, 2021
    Submitted on: January 8, 2020
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 485 times.
    This article's PDF has been downloaded 273 times.