Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436882 | Theoretical Computer Science | 2013 | 4 Pages |
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