# On Fulkerson conjecture

Jean-Luc Fouquet; Jean-Marie Vanherpe

Discussiones Mathematicae Graph Theory (2011)

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

## Access Full Article

top## Abstract

top## How to cite

topJean-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] 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] 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] J.L. Fouquet and J.M. Vanherpe, On parsimonious edge-colouring of graphs with maximum degree three, Tech. report, LIFO, 2009. Zbl1267.05117
- [4] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194, doi: 10.1007/BF01584085. Zbl0254.90054
- [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] 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] 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] 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] 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] 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 ?

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