Hao Lin ; Xiumei Wang - Three matching intersection property for matching covered graphs

dmtcs:3728 - Discrete Mathematics & Theoretical Computer Science, January 15, 2018, Vol. 19 no. 3 - https://doi.org/10.23638/DMTCS-19-3-16
Three matching intersection property for matching covered graphsArticle

Authors: Hao Lin ; Xiumei Wang

    In connection with Fulkerson's conjecture on cycle covers, Fan and Raspaud proposed a weaker conjecture: For every bridgeless cubic graph $G$, there are three perfect matchings $M_1$, $M_2$, and $M_3$ such that $M_1\cap M_2 \cap M_3=\emptyset$. We call the property specified in this conjecture the three matching intersection property (and 3PM property for short). We study this property on matching covered graphs. The main results are a necessary and sufficient condition and its applications to characterization of special graphs, such as the Halin graphs and 4-regular graphs.


    Volume: Vol. 19 no. 3
    Section: Graph Theory
    Published on: January 15, 2018
    Accepted on: December 12, 2017
    Submitted on: June 22, 2017
    Keywords: Mathematics - Combinatorics,05C70

    Consultation statistics

    This page has been seen 492 times.
    This article's PDF has been downloaded 602 times.