×

Treelike snarks. (English) Zbl 1351.05068

Summary: We study snarks whose edges cannot be covered by fewer than five perfect matchings. L. Esperet and G. Mazzuoccolo [J. Graph Theory 77, No. 2, 144–157 (2014; Zbl 1310.05089)] found an infinite family of such snarks, generalising an example provided by J. Hägglund [Electron. J. Comb. 23, No. 2, Research Paper P2.6, 10 p. (2016; Zbl 1335.05064)]. We construct another infinite family, arising from a generalisation in a different direction. The proof that this family has the requested property is computer-assisted. In addition, we prove that the snarks from this family (we call them treelike snarks) have circular flow number \(\phi_C (G)\geq 5\) and admit a 5-cycle double cover.

MSC:

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

References:

[1] M. Abreu, D. Labbate, R. Rizzi and J. Sheehan. Odd 2-factored snarks. European J. Combin. 36:460-472, 2014. · Zbl 1284.05206
[2] J.A. Bondy and U.S.R. Murty. Graph Theory. Springer Series: Graduate Texts in Mathematics, Vol. 244, 2008. · Zbl 1134.05001
[3] A. Bonisoli and D. Cariolaro. Excessive factorizations of regular graphs. A. Bondy et al. (Eds.), Graph theory in Paris, Birkh¨auser, Basel, 73-84, 2007. the electronic journal of combinatorics 23(3) (2016), #P3.5417 · Zbl 1112.05085
[4] G. Brinkmann, J. Goedgebeur, J. H¨agglund and K. Markstr¨om. Generation and properties of snarks. J. Combin. Theory Ser. B 103(4):468-488, 2013. · Zbl 1301.05119
[5] U.A. Celmins. On cubic graphs that do not have an edge 3-coloring. PhD thesis, University of Waterloo, 1984.
[6] G. Cornu´ejols, D. Naddef and W. R. Pulleyblank. Halin graphs and the Travelling Salesman Problem. Math. Prog. 26:287-294, 1983. · Zbl 0506.90083
[7] L. Esperet and G. Mazzuoccolo. On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings. J. Graph Theory 77:144-157, 2014. · Zbl 1310.05089
[8] L. Esperet, G. Mazzuoccolo and M. Tarsi. The structure of graphs with circular flow number 5 or more, and the complexity of their recognition problem. J. Comb. 7:453-479, 2016. · Zbl 1336.05053
[9] J.L. Fouquet and J.M. Vanherpe. On the perfect matching index of a bridgeless cubic graph. ManuscriptarXiv:0904.1296, 2009.
[10] D. R. Fulkerson. Blocking and anti-blocking pairs of polyhedra. Math. Prog. 1:168– 194, 1971. · Zbl 0254.90054
[11] L.A. Goddyn, M. Tarsi and C.Q. Zhang. On (k, d)-colorings and fractional nowherezero flows. J. Graph Theory 28 (3): 155-161, 1998. · Zbl 0922.05027
[12] J. H¨agglund. On snarks that are far from being 3-edge colorable. Electron. J. Combin. 23(2):#P2.6, 2016. · Zbl 1335.05064
[13] R. Halin.Uber simpliziale Zerf¨¨allungen beliebiger (endlicher oder unendlicher) Graphen. Math. Ann. 156:216-225, 1964. · Zbl 0125.11605
[14] D.A. Holton and J. Sheehan. The Petersen Graph. Australian Mathematical Society Lecture Series, 7. Cambridge University Press, Cambridge, 1993. · Zbl 0781.05001
[15] X. Hou, H.J. Lai and C.Q. Zhang. On perfect matching coverings and even subgraph coverings. J. Graph Theory 81(1):83-91, 2015. · Zbl 1330.05128
[16] T. Kaiser and A. Raspaud. Perfect matchings with restricted intersection in cubic graphs. European J. Combin. 31:1307-1315, 2010. · Zbl 1218.05137
[17] M. Kochol. Snarks without small cycles. J. Combin. Theory Ser. B. 67(1):34-47, 1996. · Zbl 0855.05066
[18] E. M´aˇcajov´a and A. Raspaud. On the strong circular 5-flow conjecture. J. Graph Theory 52(4): 307-316, 2006. · Zbl 1098.05031
[19] G. Mazzuoccolo. The equivalence of two conjectures of Berge and Fulkerson. J. Graph Theory 68 (2011), 125-128. · Zbl 1230.05238
[20] M. Preissmann. Sur les colorations des arˆetes des graphes cubiques. Th‘ese de doctorat de 3‘emecycle, Grenoble, 1981.
[21] E. Steffen. 1-factor and cycle covers of cubic graphs. J. Graph Theory 78 (2014), 195-206. · Zbl 1309.05108
[22] W.T. Tutte. A contribution to the theory of chromatic polynomials. Canad. J. Math. 6 (1954), 80-91. the electronic journal of combinatorics 23(3) (2016), #P3.5418 · Zbl 0055.17101
[23] C.Q. Zhang. Integer Flows and Cycle Covers of Graphs. Volume 205 of Monographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker, New York, 1997.
[24] C.Q. Zhang. Circuit Double Cover of Graphs. London Math. Soc. Lecture Note Ser., vol. 399, Cambridge Univ. Press, 2012. · Zbl 1250.05006
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.