Discussiones Mathematicae Graph Theory 31(2) (2011)
253-272
doi: 10.7151/dmgt.1543
Jean-Luc Fouquet and Jean-Marie Vanherpe
L.I.F.O., Faculté des Sciences, B.P. 6759
Université d'Orléans
45067 Orléans Cedex 2, France
Moreover, we give a simple proof that the Fulkerson conjecture holds true for some classes of well known snarks.
Keywords: cubic graph, perfect matchings.
2010 Mathematics Subject Classification: 05C15, 05C70.
[1] | V. Chvátal, Flip-Flops on hypohamiltonian graphs, Canad. Math. Bull. 16 (1973) 33-41, doi: 10.4153/CMB-1973-008-9. |
[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. |
[3] | J.L. Fouquet and J.M. Vanherpe, On parsimonious edge-colouring of graphs with maximum degree three, Tech. report, LIFO, 2009. |
[4] | D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194, doi: 10.1007/BF01584085. |
[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. |
[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. |
[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 . |
[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. |
Received 8 December 2009
Revised 2 April 2010
Accepted 6 April 2010