Reduction of the Berge-Fulkerson conjecture to cyclically 5-edge-connected snarks

Máčajová, Edita; Mazzuoccolo, Giuseppe

doi:10.1090/proc/15057

Reduction of the Berge-Fulkerson conjecture to cyclically 5-edge-connected snarks
HTML articles powered by AMS MathViewer

by Edita Máčajová and Giuseppe Mazzuoccolo PDF

Proc. Amer. Math. Soc. 148 (2020), 4643-4652 Request permission

Abstract:

The Berge-Fulkerson conjecture, originally formulated in the language of mathematical programming, asserts that the edges of every bridgeless cubic ($3$-valent) graph can be covered with six perfect matchings in such a way that every edge is in exactly two of them. As with several other classical conjectures in graph theory, every counterexample to the Berge-Fulkerson conjecture must be a non-$3$-edge-colorable cubic graph. In contrast to Tutte’s 5-flow conjecture and the cycle double conjecture, no nontrivial reduction is known for the Berge-Fulkerson conjecture. In the present paper, we prove that a possible minimum counterexample to the conjecture must be cyclically $5$-edge-connected.

References

Igor V. Dolgachev, Abstract configurations in algebraic geometry, The Fano Conference, Univ. Torino, Turin, 2004, pp. 423–462. MR 2112585
Jack Edmonds, Maximum matching and a polyhedron with $0,1$-vertices, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 125–130. MR 183532
Genghua Fan and André Raspaud, Fulkerson’s conjecture and circuit covers, J. Combin. Theory Ser. B 61 (1994), no. 1, 133–138. MR 1275273, DOI 10.1006/jctb.1994.1039
Jean-Luc Fouquet and Jean-Marie Vanherpe, On Fulkerson conjecture, Discuss. Math. Graph Theory 31 (2011), no. 2, 253–272. MR 2865657, DOI 10.7151/dmgt.1543
D. R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971), 168–194. MR 294149, DOI 10.1007/BF01584085
Rongxia Hao, Jianbing Niu, Xiaofeng Wang, Cun-Quan Zhang, and Taoye Zhang, A note on Berge-Fulkerson coloring, Discrete Math. 309 (2009), no. 13, 4235–4240. MR 2519156, DOI 10.1016/j.disc.2008.12.024
Rong-Xia Hao, Cun-Quan Zhang, and Ting Zheng, Berge-Fulkerson coloring for $C_{(8)}$-linked graphs, J. Graph Theory 88 (2018), no. 1, 46–60. MR 3781603, DOI 10.1002/jgt.22184
Andreas Huck, Reducible configurations for the cycle double cover conjecture, Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997), 2000, pp. 71–90. MR 1743825, DOI 10.1016/S0166-218X(99)00126-2
François Jaeger, Nowhere-zero flow problems, Selected topics in graph theory, 3, Academic Press, San Diego, CA, 1988, pp. 71–95. MR 1205397
Kaio Karam and C. N. Campos, Fulkerson’s conjecture and Loupekine snarks, Discrete Math. 326 (2014), 20–28. MR 3188983, DOI 10.1016/j.disc.2014.02.016
Martin Kochol, Reduction of the 5-flow conjecture to cyclically 6-edge-connected snarks, J. Combin. Theory Ser. B 90 (2004), no. 1, 139–145. Dedicated to Adrian Bondy and U. S. R. Murty. MR 2041322, DOI 10.1016/S0095-8956(03)00080-7
Martin Kochol, Smallest counterexample to the 5-flow conjecture has girth at least eleven, J. Combin. Theory Ser. B 100 (2010), no. 4, 381–389. MR 2644241, DOI 10.1016/j.jctb.2009.12.001
Daniel Kráľ, Edita Máčajová, Ondřej Pangrác, André Raspaud, Jean-Sébastien Sereni, and Martin Škoviera, Projective, affine, and abelian colorings of cubic graphs, European J. Combin. 30 (2009), no. 1, 53–69. MR 2460217, DOI 10.1016/j.ejc.2007.11.029
G. Mazzuoccolo, The equivalence of two conjectures of Berge and Fulkerson, J. Graph Theory 68 (2011), no. 2, 125–128. MR 2833954, DOI 10.1002/jgt.20545
Stanley E. Payne and Joseph A. Thas, Finite generalized quadrangles, 2nd ed., EMS Series of Lectures in Mathematics, European Mathematical Society (EMS), Zürich, 2009. MR 2508121, DOI 10.4171/066
Julius Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891), no. 1, 193–220 (German). MR 1554815, DOI 10.1007/BF02392606
T. Schönberger, Ein Beweis des Petersenschen Graphensatzes, Acta Litt. Sci. Szeged 7 (1934), 51–57.
P. D. Seymour, On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. (3) 38 (1979), no. 3, 423–460. MR 532981, DOI 10.1112/plms/s3-38.3.423
P. D. Seymour, Sums of circuits, Graph Theory and Related Topics 1 (1979), 341–355.
G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Austral. Math. Soc. 8 (1973), 367–387. MR 325438, DOI 10.1017/S0004972700042660
W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954), 80–91. MR 61366, DOI 10.4153/cjm-1954-010-9