Download PDF - Mácajová and Škoviera conjecture on cubic graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Mácajová and Škoviera conjecture on cubic graphs

Authors 1, 1

Affiliations

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

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.

Keywords

ENG
Cubic graph, edge-partition, traceable graphs

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2010/30/2
Export to PBN, Opens in new tab
Pages:
315-333
Main language of publication
English
Received
2008-12-31
Accepted
2009-09-12
Published
2010

DOI: 10.7151/dmgt.1496

Exact and natural sciences