A note on Fouquet-Vanherpe’s question and Fulkerson conjecture

Chen, F.

A note on Fouquet-Vanherpe’s question and Fulkerson conjecture

Document Type : Research Paper

Author

F. Chen

Institute of Statistics and Applied Mathematics‎, ‎Anhui University of Finance and Economics‎, ‎Bengbu‎, ‎Anhui‎, ‎233030‎, ‎P‎. ‎R‎. ‎China.

Abstract

‎The excessive index of a bridgeless cubic graph $G$ is the least integer $k$‎, ‎such that $G$ can be covered by $k$ perfect matchings‎. ‎An equivalent form of Fulkerson conjecture (due to Berge) is that every bridgeless‎ ‎cubic graph has excessive index at most five‎. ‎Clearly‎, ‎Petersen graph is a cyclically 4-edge-connected snark with excessive index at least 5‎, ‎so Fouquet and Vanherpe asked whether Petersen graph is the only one with that property‎. ‎H\"{a}gglund gave a negative answer to their question by constructing two graphs Blowup$(K_4‎, ‎C)$ and Blowup$(Prism‎, ‎C_4)$‎. ‎Based on the first graph‎, ‎Esperet et al‎. ‎constructed infinite families of cyclically 4-edge-connected snarks with excessive index at least five‎. ‎Based on these two graphs‎, ‎we construct infinite families of cyclically 4-edge-connected snarks $E_{0,1,2,\ldots‎, ‎(k-1)}$ in which $E_{0,1,2}$ is Esperet et al.'s construction‎. ‎In this note‎, ‎we prove that $E_{0,1,2,3}$ has excessive index at least five‎, ‎which gives a strongly negative answer to Fouquet and Vanherpe's question‎. ‎As a subcase of Fulkerson conjecture‎, ‎H\"{a}ggkvist conjectured that every cubic hypohamiltonian graph has a Fulkerson-cover‎. ‎Motivated by a related result due to Hou et al.'s‎, ‎in this note we prove that Fulkerson conjecture holds on some families of bridgeless cubic graphs.

Keywords

Main Subjects

05-XX Combinatorics

References

D. Blanu_sa, Problem ceteriju boja (The problem of four colors), Hrvatsko Prirodoslovno Dru_stvo Glasnik Mat-Fiz. Astr. Ser. 1 (1946) 31--42.

J. A. Bondy and U. S .R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976.

A. Bonisoli and D. Cariolaro, Excessive factorizations of regular graphs, Graph Theory in Paris, 73--84, Birkhauser Basel, 2007.

L. Esperet and G. Mazzuoccolo, On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings, J. Graph Theory 77 (2014), no. 2, 144--157.

J. L. Fouquet and J. M. Vanherpe, On the perfect matching index of bridgeless cubic graphs, Computing Research Repository--CORR, abs/0904.1, 2009.

D. R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Program. 1 (1971), 168--194.

J. Hagglund, On snarks that are far from being 3-edge colorable, Electron. J. Combin. 23 (2016), no. 2, 10 pages.

R. X. Hao, J. B. Niu, X. F. Wang, C. Q. Zhang and T. Y. Zhang, A note on Berge-Fulkerson coloring, Discrete Math. 309 (2009), no. 13, 4235--4240.

X. M. Hou, H. J. Lai and C. Q. Zhang, On Matching Coverings and Cycle Coverings,preprint, 2012.

G. Mazzuoccolo, The equivalence of two conjectures of Berge and Fulkerson, J. Graph Theory 68 (2011), no. 2, 125--128.

B. Mohar, R. J. Nowakowski and D. B. West, Research problems from the 5th Slovenian Conference (Bled, 2003), Discrete Math. 307 (2007), no. 3-5, 650--658.

N. Robertson, D. Sanders, P. D. Seymour and R. Thomas, Tutte's edge-colouring conjecture, J. Combin. Theory Ser. B 70 (1997), no. 1, 166--183.

P. D. Seymour, On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. Lond. Math. Soc. (3) 38 (1979), no. 3, 423--460.

C. Q. Zhang, Integer Flows and Cycle Covers of Graphs, Marcel Dekker Inc., New York, 1997.