کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436882 690047 2013 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Three-matching intersection conjecture for perfect matching polytopes of small dimensions
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Three-matching intersection conjecture for perfect matching polytopes of small dimensions
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 482, 22 April 2013, Pages 111-114