Sparsely intersecting perfect matchings in cubic graphs

被引:16
作者
Macajova, Edita [1 ]
Skoviera, Martin [1 ]
机构
[1] Comenius Univ, Fac Math Phys & Informat, Dept Comp Sci, Bratislava 84248, Slovakia
关键词
05C15; 05C70;
D O I
10.1007/s00493-014-2550-4
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In 1971, Fulkerson made a conjecture that every bridgeless cubic graph contains a family of six perfect matchings such that each edge belongs to exactly two of them; equivalently, such that no three of the matchings have an edge in common. In 1994, Fan and Raspaud proposed a weaker conjecture which requires only three perfect matchings with no edge in common. In this paper we discuss these and other related conjectures and make a step towards Fulkerson's conjecture by proving the following result: Every bridgeless cubic graph which has a 2-factor with at most two odd circuits contains three perfect matchings with no edge in common.
引用
收藏
页码:61 / 94
页数:34
相关论文
共 9 条
[1]   FULKERSON CONJECTURE AND CIRCUIT COVERS [J].
FAN, GH ;
RASPAUD, A .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 61 (01) :133-138
[2]  
Fulkerson D., 1971, MATH PROGRAM, V1, P168, DOI [10.1007/BF01584085, DOI 10.1007/BF01584085]
[3]   5 CYCLE DOUBLE COVERS OF SOME CUBIC GRAPHS [J].
HUCK, A ;
KOCHOL, M .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 64 (01) :119-125
[4]  
Kaiser T., 2007, ELECT NOTES DISCRETE, V28, P293
[5]   Perfect matchings with restricted intersection in cubic graphs [J].
Kaiser, Tomas ;
Raspaud, Andre .
EUROPEAN JOURNAL OF COMBINATORICS, 2010, 31 (05) :1307-1315
[6]   Projective, affine, and abelian colorings of cubic graphs [J].
Kral, Daniel ;
Macajova, Edita ;
Pangrac, Ondrej ;
Raspaud, Andre ;
Sereni, Jean-Sebastien ;
Skoviera, Martin .
EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (01) :53-69
[7]   Fano colourings of cubic graphs and the Fulkerson Conjecture [J].
Mácajová, E ;
Skoviera, M .
THEORETICAL COMPUTER SCIENCE, 2005, 349 (01) :112-120
[8]  
Petersen J., 1891, ACTA MATH, V15, P193, DOI [DOI 10.1007/BF02392606, 10.1007/BF02392606]
[9]  
SEYMOUR PD, 1979, P LOND MATH SOC, V38, P423