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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1496,
author = {Jean-Luc Fouquet and Jean-Marie Vanherpe},
title = {M\'acajov\'a and \v Skoviera conjecture on cubic graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {30},
year = {2010},
pages = {315-333},
zbl = {1214.05117},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1496}
}
Jean-Luc Fouquet; Jean-Marie Vanherpe. Mácajová and Škoviera conjecture on cubic graphs. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 315-333. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1496/
[000] [1] J.A. Bondy and U.S.R. Murty, Graph Theory, volume 244 of Graduate Text in Mathematics (Springer, 2008).
[001] [2] J. Edmonds, Maximum matching and a polyhedron with (0,1) vertices, J. Res. Nat. Bur. Standards (B) 69 (1965) 125-130. | Zbl 0141.21802
[002] [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. | Zbl 0811.05053
[003] [4] J.L. Fouquet and J.M. Vanherpe, On Fan Raspaud Conjecture, manuscript, 2008.
[004] [5] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194, doi: 10.1007/BF01584085. | Zbl 0254.90054
[005] [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. | Zbl 1200.05172
[006] [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. | Zbl 1291.05158
[007] [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. | Zbl 1082.05040
[008] [9] E. Màcajová and M. Skoviera, http://garden.irmacs.sfu.ca/?q=op/intersecting two perfect matchings, 2007.
[009] [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. | Zbl 0411.05037