ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 30(2) (2010) 315-333
DOI: 10.7151/dmgt.1496

Mácajová and Skoviera Conjecture on Cubic Graphs

Jean-Luc Fouquet  and  Jean-Marie Vanherpe

L.I.F.O., Faculté des Sciences, B.P. 6759
Université d'Orléans, 45067 Orléans Cedex 2, France


A conjecture of Mácajová and Skoviera asserts that every bridgeless cubic graph has two perfect matchings whose intersection does not contain any odd edge cut. We prove this conjecture for graphs with few vertices and we give a stronger result for traceable graphs.

Keywords: Cubic graph, edge-partition, traceable graphs.

2010 Mathematics Subject Classification: 05C30, 05C70.


[1] J.A. Bondy and U.S.R. Murty, Graph Theory, volume 244 of Graduate Text in Mathematics (Springer, 2008).
[2] J. Edmonds, Maximum matching and a polyhedron with (0,1) vertices, J. Res. Nat. Bur. Standards (B) 69 (1965) 125-130.
[3] G. Fan and A. Raspaud, Fulkerson's conjecture and circuit covers, J. Combin. Theory (B) 61 (1994) 133-138, doi: 10.1006/jctb.1994.1039.
[4] J.L. Fouquet and J.M. Vanherpe, On Fan Raspaud Conjecture, manuscript, 2008.
[5] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194, doi: 10.1007/BF01584085.
[6] T. Kaiser, D. Král and S. Norine, Unions of perfect matchings in cubic graphs, Electronic Notes in Discrete Math. 22 (2005) 341-345, doi: 10.1016/j.endm.2005.06.079.
[7] T. Kaiser and A. Raspaud, Non-intersecting perfect matchings in cubic graphs, Electronic Notes in Discrete Math. 28 (2007) 293-299, doi: 10.1016/j.endm.2007.01.042.
[8] E. Màcajová and M. Skoviera, Fano colourings of cubic graphs and the Fulkerson conjecture, Theor. Comput. Sci. 349 (2005) 112-120, doi: 10.1016/j.tcs.2005.09.034.
[9] E. Màcajová and M. Skoviera, two perfect matchings, 2007.
[10] P. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. 38 (1979) 423-460, doi: 10.1112/plms/s3-38.3.423.

Received 31 December 2008
Revised 12 September 2009
Accepted 9 November 2009