×

Reduction of the Berge-Fulkerson conjecture to cyclically 5-edge-connected snarks. (English) Zbl 1447.05172

Summary: 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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dolgachev, Igor V., Abstract configurations in algebraic geometry. The Fano Conference, 423-462 (2004), Univ. Torino, Turin · Zbl 1068.14059
[2] Edmonds, Jack, Maximum matching and a polyhedron with \(0,1\)-vertices, J. Res. Nat. Bur. Standards Sect. B, 69B, 125-130 (1965) · Zbl 0141.21802
[3] Fan, Genghua; Raspaud, Andr\'{e}, Fulkerson’s conjecture and circuit covers, J. Combin. Theory Ser. B, 61, 1, 133-138 (1994) · Zbl 0811.05053 · doi:10.1006/jctb.1994.1039
[4] Fouquet, Jean-Luc; Vanherpe, Jean-Marie, On Fulkerson conjecture, Discuss. Math. Graph Theory, 31, 2, 253-272 (2011) · Zbl 1234.05185 · doi:10.7151/dmgt.1543
[5] Fulkerson, D. R., Blocking and anti-blocking pairs of polyhedra, Math. Programming, 1, 168-194 (1971) · Zbl 0254.90054 · doi:10.1007/BF01584085
[6] Hao, Rongxia; Niu, Jianbing; Wang, Xiaofeng; Zhang, Cun-Quan; Zhang, Taoye, A note on Berge-Fulkerson coloring, Discrete Math., 309, 13, 4235-4240 (2009) · Zbl 1209.05084 · doi:10.1016/j.disc.2008.12.024
[7] Hao, Rong-Xia; Zhang, Cun-Quan; Zheng, Ting, Berge-Fulkerson coloring for \(C_{(8)} \)-linked graphs, J. Graph Theory, 88, 1, 46-60 (2018) · Zbl 1451.05081 · doi:10.1002/jgt.22184
[8] Huck, Andreas, Reducible configurations for the cycle double cover conjecture, Discrete Appl. Math.. Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997), 99, 1-3, 71-90 (2000) · Zbl 0966.05045 · doi:10.1016/S0166-218X(99)00126-2
[9] Jaeger, Fran\c{c}ois, Nowhere-zero flow problems. Selected topics in graph theory, 3, 71-95 (1988), Academic Press, San Diego, CA · Zbl 0658.05034
[10] Karam, Kaio; Campos, C. N., Fulkerson’s conjecture and Loupekine snarks, Discrete Math., 326, 20-28 (2014) · Zbl 1288.05144 · doi:10.1016/j.disc.2014.02.016
[11] Kochol, Martin, Reduction of the 5-flow conjecture to cyclically 6-edge-connected snarks, J. Combin. Theory Ser. B, 90, 1, 139-145 (2004) · Zbl 1033.05067 · doi:10.1016/S0095-8956(03)00080-7
[12] Kochol, Martin, Smallest counterexample to the 5-flow conjecture has girth at least eleven, J. Combin. Theory Ser. B, 100, 4, 381-389 (2010) · Zbl 1211.05055 · doi:10.1016/j.jctb.2009.12.001
[13] Kr\'{a}\v{l}, Daniel; M\'{a}\v{c}ajov\'{a}, Edita; Pangr\'{a}c, Ond\v{r}ej; Raspaud, Andr\'{e}; Sereni, Jean-S\'{e}bastien; Skoviera, Martin, Projective, affine, and abelian colorings of cubic graphs, European J. Combin., 30, 1, 53-69 (2009) · Zbl 1198.05019 · doi:10.1016/j.ejc.2007.11.029
[14] Mazzuoccolo, G., The equivalence of two conjectures of Berge and Fulkerson, J. Graph Theory, 68, 2, 125-128 (2011) · Zbl 1230.05238 · doi:10.1002/jgt.20545
[15] Payne, Stanley E.; Thas, Joseph A., Finite generalized quadrangles, EMS Series of Lectures in Mathematics, xii+287 pp. (2009), European Mathematical Society (EMS), Z\"{u}rich · Zbl 1247.05047 · doi:10.4171/066
[16] Petersen, Julius, Die Theorie der regul\"{a}ren graphs, Acta Math., 15, 1, 193-220 (1891) · JFM 23.0115.03 · doi:10.1007/BF02392606
[17] Schonberger T. Sch\"onberger, Ein Beweis des Petersenschen Graphensatzes, Acta Litt. Sci. Szeged 7 (1934), 51-57. · JFM 60.1217.06
[18] Seymour, P. D., On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. (3), 38, 3, 423-460 (1979) · Zbl 0411.05037 · doi:10.1112/plms/s3-38.3.423
[19] Sey P. D. Seymour, Sums of circuits, Graph Theory and Related Topics 1 (1979), 341-355. · Zbl 0465.05042
[20] Szekeres, G., Polyhedral decompositions of cubic graphs, Bull. Austral. Math. Soc., 8, 367-387 (1973) · Zbl 0249.05111 · doi:10.1017/S0004972700042660
[21] Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101 · doi:10.4153/cjm-1954-010-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.