Article ID Journal Published Year Pages File Type
436882 Theoretical Computer Science 2013 4 Pages PDF
Abstract

In the study of Fulkerson’s conjecture, Fan and Raspaud (1994) proposed a weaker conjecture: in every bridgeless cubic graph G, there are three perfect matchings M1, M2, and M3 such that M1∩M2∩M3=0̸. In this note we prove that this conjecture is true if the dimension of the perfect matching polytope of G is at most 9. This includes the class of bridgeless cubic graphs with the property that all the vertices of the corresponding perfect matching polytope are affinely independent.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics