Geodesic
Mácajová and Škoviera conjecture on cubic graphs
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 2, pp. 315-333.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2010_30_2_a11,
     author = {Fouquet, Jean-Luc and Vanherpe, Jean-Marie},
     title = {M\'acajov\'a and {\v{S}koviera} conjecture on cubic graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {315--333},
     publisher = {mathdoc},
     volume = {30},
     number = {2},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a11/}
}
TY  - JOUR
AU  - Fouquet, Jean-Luc
AU  - Vanherpe, Jean-Marie
TI  - Mácajová and Škoviera conjecture on cubic graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 315
EP  - 333
VL  - 30
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a11/
LA  - en
ID  - DMGT_2010_30_2_a11
ER  - 
%0 Journal Article
%A Fouquet, Jean-Luc
%A Vanherpe, Jean-Marie
%T Mácajová and Škoviera conjecture on cubic graphs
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 315-333
%V 30
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a11/
%G en
%F DMGT_2010_30_2_a11
Fouquet, Jean-Luc; Vanherpe, Jean-Marie. Mácajová and Škoviera conjecture on cubic graphs. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 2, pp. 315-333. http://geodesic.mathdoc.fr/item/DMGT_2010_30_2_a11/

[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, http://garden.irmacs.sfu.ca/?q=op/intersecting 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.