Mácajová and Škoviera conjecture on cubic graphs

Jean-Luc Fouquet; Jean-Marie Vanherpe

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 2, page 315-333
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Jean-Luc Fouquet, and Jean-Marie Vanherpe. "Mácajová and Škoviera conjecture on cubic graphs." Discussiones Mathematicae Graph Theory 30.2 (2010): 315-333. <http://eudml.org/doc/271076>.

@article{Jean2010,
abstract = {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.},
author = {Jean-Luc Fouquet, Jean-Marie Vanherpe},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Cubic graph; edge-partition; traceable graphs; cubic graph},
language = {eng},
number = {2},
pages = {315-333},
title = {Mácajová and Škoviera conjecture on cubic graphs},
url = {http://eudml.org/doc/271076},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Jean-Luc Fouquet
AU - Jean-Marie Vanherpe
TI - Mácajová and Škoviera conjecture on cubic graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 2
SP - 315
EP - 333
AB - 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.
LA - eng
KW - Cubic graph; edge-partition; traceable graphs; cubic graph
UR - http://eudml.org/doc/271076
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory, volume 244 of Graduate Text in Mathematics (Springer, 2008). 
  2. [2] J. Edmonds, Maximum matching and a polyhedron with (0,1) vertices, J. Res. Nat. Bur. Standards (B) 69 (1965) 125-130. Zbl0141.21802
  3. [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. Zbl0811.05053
  4. [4] J.L. Fouquet and J.M. Vanherpe, On Fan Raspaud Conjecture, manuscript, 2008. 
  5. [5] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194, doi: 10.1007/BF01584085. Zbl0254.90054
  6. [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. Zbl1200.05172
  7. [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. Zbl1291.05158
  8. [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. Zbl1082.05040
  9. [9] E. Màcajová and M. Skoviera, http://garden.irmacs.sfu.ca/?q=op/intersecting two perfect matchings, 2007. 
  10. [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. Zbl0411.05037

NotesEmbed ?

top

You must be logged in to post comments.