×

Families of dot-product snarks on orientable surfaces of low genus. (English) Zbl 1124.05028

Summary: We introduce a generalized dot-product and provide some embedding conditions under which the genus of a graph does not rise under a dot-product with the Petersen graph. Using these conditions, we disprove a conjecture of Tinsley and Watkins on the genus of dot-products of the Petersen graph [see C. Tinsley and J. J. Watkins, Graphs and applications, Proc. 1st Symp. Graph Theory, Boulder/Colo. 1982, 317–332 (1985; Zbl 0558.05016)] and show that both Grünbaum’s conjecture and the Berge-Fulkerson conjecture hold for certain infinite families of snarks. Additionally, we determine the orientable genus of four known snarks and two known snark families, construct a new example of an infinite family of snarks on the torus, and construct ten new examples of infinite families of snarks on the 2-holed torus; these last constructions allow us to show that there are genus-2 snarks of every even order \(n \geq 18\).

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory

Citations:

Zbl 0558.05016
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albertson, M.O., Stromquist, W.R.: Locally planar toroidal graphs are 5-colorable, Proc. Amer. Math. Soc. 84, 449–457 (1982) · Zbl 0518.05031
[2] Archdeacon, D.: Problems in topological graph theory: Three-Edge-Coloring Orientable Triangulations, http://www.emba.uvm.edu/\(\sim\)archdeac/problems/grunbaum.htm
[3] Chetwynd, A.G., Wilson, R.J.: Snarks and supersnarks, In: The Theory and Applications of Graphs (Kalamazoo, Mich., 1980), pp. 215–241, Wiley, New York, 1981
[4] Decker, R.: On the orientable genus of a graph, Ph.D. Thesis, Ohio State University, 1978
[5] Fisk, S., Mohar, B.: Coloring graphs without short nonbounding cycles, J. Combin. Theory Ser. B 60(2), 268–276 (1994) · Zbl 0793.05058
[6] Fulkerson, D.R.: Blocking and anti-blocking pairs of polyhedra, Math. Program. 1, 168–194 (1971) · Zbl 0254.90054
[7] Grünbaum, B.: Conjecture 6. In: Tutte, W.T. (ed.) Recent Progress in Combinatorics, p. 343. Academic Press, New York, 1969 · Zbl 0187.44202
[8] Hutchinson, J.P.: Three-coloring graphs embedded on surfaces with all faces even-sided, J. Combin. Theory Ser. B 65(1), 139–155 (1995) · Zbl 0828.05029
[9] Isaacs, R.: Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82, 221–239 (1975) · Zbl 0311.05109
[10] Kaminski, J.: Genus of each of the 22-vertex snarks, in preparation
[11] Mohar, B., Vodopivec, A.: On polyhedral embeddings of cubic graphs, preprint, www.fmf.uni-lj.si/\(\sim\)mohar/Papers/PolyhedralEmbeddings.pdf · Zbl 1108.05033
[12] Orbanić, A., Pisanski, T., Randić, B., Servatius, B.: Blanusa double, Math. Commun. 9, 91–103 (2004) · Zbl 1058.05019
[13] Robertson, N., Seymour, P.D.: Generalizing Kuratowski’s theorem, Congr. Numer. 45, 129–138 (1984) · Zbl 0557.05033
[14] Szekeres, G.: Non-colourable trivalent graphs, In Combinatorial mathematics, III (Proc. Third Australian Conf., Univ. Queensland, St. Lucia, 1974), pp. 227–233, Lecture Notes in Math., vol. 452, Springer, Berlin, 1975 · Zbl 0306.05104
[15] Thomassen, C.: Five-coloring maps on surfaces, J. Combin. Theory Ser. B 59(1), 89–105 (1993) · Zbl 0794.05026
[16] Thomassen, C.: Five-coloring graphs on the torus, J. Combin. Theory Ser. B 62(1), 11–33 (1994) · Zbl 0805.05022
[17] Tinsley, F.C., Watkins, J.J.: A study of snark embeddings, In: Graphs and Applications (Boulder, Colo., 1982), pp. 317–332, Wiley, New York, 1985 · Zbl 0558.05016
[18] Vodopivec, A.: On embeddings of snarks in the torus, preprint, http://www.ijp.si/ ftp/pub/preprints/ps/2004/pp921.ps · Zbl 1154.05024
[19] Watkins, J.J., Tinsley, F.C., Richardson, D.M.: The non-orientable genus of the flower snarks. In Combinatorics, Graph Theory, and Algorithms, Vol. I, II (Kalamazoo, MI, 1996), pp. 711–721, New Issues Press, Kalamazoo, MI, 1999
[20] Watkins, J.J., Wilson, R.J.: A survey of snarks. In: Graph Theory, Combinatorics, and Applications. Vol. 2 (Kalamazoo, MI, 1988), pp. 1129–1144, Wiley, New York, 1991 · Zbl 0841.05035
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.