paper

Three matching intersection property for matching covered graphs

arXiv:1611.09531 · doi:10.23638/DMTCS-19-3-16

Abstract

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.

7 pages