On Fulkerson conjecture

Jean-Luc Fouquet; Jean-Marie Vanherpe

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 2, page 253-272
  • ISSN: 2083-5892

Abstract

top
If G is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings (a Fulkerson covering) with the property that every edge of G is contained in exactly two of them. A consequence of the Fulkerson conjecture would be that every bridgeless cubic graph has 3 perfect matchings with empty intersection (this problem is known as the Fan Raspaud Conjecture). A FR-triple is a set of 3 such perfect matchings. We show here how to derive a Fulkerson covering from two FR-triples. Moreover, we give a simple proof that the Fulkerson conjecture holds true for some classes of well known snarks.

How to cite

top

Jean-Luc Fouquet, and Jean-Marie Vanherpe. "On Fulkerson conjecture." Discussiones Mathematicae Graph Theory 31.2 (2011): 253-272. <http://eudml.org/doc/270931>.

@article{Jean2011,
abstract = {If G is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings (a Fulkerson covering) with the property that every edge of G is contained in exactly two of them. A consequence of the Fulkerson conjecture would be that every bridgeless cubic graph has 3 perfect matchings with empty intersection (this problem is known as the Fan Raspaud Conjecture). A FR-triple is a set of 3 such perfect matchings. We show here how to derive a Fulkerson covering from two FR-triples. Moreover, we give a simple proof that the Fulkerson conjecture holds true for some classes of well known snarks.},
author = {Jean-Luc Fouquet, Jean-Marie Vanherpe},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {cubic graph; perfect matchings; Fulkerson covering; Fan-Raspaud triple; FR-triple},
language = {eng},
number = {2},
pages = {253-272},
title = {On Fulkerson conjecture},
url = {http://eudml.org/doc/270931},
volume = {31},
year = {2011},
}

TY - JOUR
AU - Jean-Luc Fouquet
AU - Jean-Marie Vanherpe
TI - On Fulkerson conjecture
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 2
SP - 253
EP - 272
AB - If G is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings (a Fulkerson covering) with the property that every edge of G is contained in exactly two of them. A consequence of the Fulkerson conjecture would be that every bridgeless cubic graph has 3 perfect matchings with empty intersection (this problem is known as the Fan Raspaud Conjecture). A FR-triple is a set of 3 such perfect matchings. We show here how to derive a Fulkerson covering from two FR-triples. Moreover, we give a simple proof that the Fulkerson conjecture holds true for some classes of well known snarks.
LA - eng
KW - cubic graph; perfect matchings; Fulkerson covering; Fan-Raspaud triple; FR-triple
UR - http://eudml.org/doc/270931
ER -

References

top
  1. [1] V. Chvátal, Flip-Flops on hypohamiltonian graphs, Canad. Math. Bull. 16 (1973) 33-41, doi: 10.4153/CMB-1973-008-9. Zbl0253.05142
  2. [2] 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
  3. [3] J.L. Fouquet and J.M. Vanherpe, On parsimonious edge-colouring of graphs with maximum degree three, Tech. report, LIFO, 2009. Zbl1267.05117
  4. [4] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194, doi: 10.1007/BF01584085. Zbl0254.90054
  5. [5] M.K. Goldberg, Construction of class 2 graphs with maximum vertex degree 3, J. Combin. Theory (B) 31 (1981) 282-291, doi: 10.1016/0095-8956(81)90030-7. Zbl0449.05037
  6. [6] R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait colorable, Am. Math. Monthly 82 (1975) 221-239, doi: 10.2307/2319844. Zbl0311.05109
  7. [7] R. Rizzi, Indecomposable r-graphs and some other counterexamples, J. Graph Theory 32 (1999) 1-15, doi: 10.1002/(SICI)1097-0118(199909)32:1<1::AID-JGT1>3.0.CO;2-B Zbl0932.05072
  8. [8] Z. Skupień Exponentially many hypohamiltonian graphs, Graphs, Hypergraphs and Matroids III (M. Borowiecki and Z. Skupień, eds.) Proc. Conf. Kalsk, 1988, Higher College of Enginering, Zielona Góra, 1989, pp. 123-132. 
  9. [9] J.J. Watkins, Snarks, Graph Theory and Its Applications: East and West (Jinan, 1986), Ann. New York Acad. Sci. vol. 576, New York Acad. Sci. (New York, 1989) pp. 606-622. 
  10. [10] R. Hao, J. Niu, X. Wang, C.-Q. Zhang and T. Zhang, A note on Berge-Fulkerson coloring, Discrete Math. 309 (2009) 4235-4240, doi: 10.1016/j.disc.2008.12.024. Zbl1209.05084

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.