×

zbMATH — the first resource for mathematics

Irreducible snarks of given order and cyclic connectivity. (English) Zbl 1092.05026
Summary: A snark is a “nontrivial” cubic graph whose edges cannot be properly coloured by three colours; it is irreducible if each nontrivial edge-cut divides the snark into colourable components. Irreducible snarks can be viewed as simplest uncolourable structures. In fact, all snarks can be composed from irreducible snarks in a suitable way. In this paper we deal with the problem of the existence of irreducible snarks of given order and cyclic connectivity. We determine all integers \(n\) for which there exists an irreducible snark of order \(n\), and construct irreducible snarks with cyclic connectivity 4 and 5 of all possible orders. Moreover, we construct cyclically 6-connected irreducible snarks of each even order \(\geqslant 210\). (Cyclically 7-connected snarks are believed not to exist.)

MSC:
05C15 Coloring of graphs and hypergraphs
Keywords:
edge-colouring
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brinkmann, G., Catalogue of snarks of the orders 10-30 electronic document, (1998), Universität Bielefeld Bielefeld
[2] Brinkmann, G.; Steffen, E., Snarks and reducibility, Ars combin., 50, 292-296, (1998) · Zbl 0963.05050
[3] Cameron, P.J.; Chetwynd, A.G.; Watkins, J.J., Decomposition of snarks, J. graph theory, 11, 13-19, (1987) · Zbl 0612.05030
[4] M. Chladný, M. Škoviera, Factorisation of snarks, submitted for publication.
[5] Descartes, B., Network colourings, Math. gaz., 32, 67-69, (1948) · Zbl 0030.37601
[6] Diestel, R., Graph theory, (2000), Springer New York · Zbl 0945.05002
[7] Fouquet, J.L., Note sur la existence d’un snark d’ordre 16, Discrete math., 38, 163-171, (1982) · Zbl 0471.05036
[8] Goldberg, M.K., Construction of class 2 graphs with maximum vertex degree 3, J. combin. theory ser. B, 31, 282-291, (1981) · Zbl 0449.05037
[9] Holton, D.A.; Sheehan, J., The Petersen graph, (1993), Cambridge University Press Cambridge, MA · Zbl 0781.05001
[10] Holyer, I., NP-completeness of edge-colouring, SIAM J. comput., 10, 718-720, (1981) · Zbl 0473.68034
[11] Isaacs, R., Infinite families of non-trivial trivalent graphs which are not Tait colorable, Amer. math. monthly, 82, 221-239, (1975) · Zbl 0311.05109
[12] Jaeger, F.; Swart, T., Problem session, Ann. discrete math., 9, 305, (1980)
[13] Kochol, M., A cyclically 6-edge-connected snark of order 118, Discrete math., 161, 297-300, (1996) · Zbl 0870.05025
[14] Kochol, M., Snarks without small cycles, J. combin. theory ser. B, 67, 34-47, (1996) · Zbl 0855.05066
[15] Nedela, R.; Škoviera, M., Decompositions and reductions of snarks, J. graph theory, 22, 253-279, (1996) · Zbl 0856.05082
[16] Robinson, R.W.; Wormald, N.C., Almost all cubic graphs are Hamiltonian, Random struct. algebra, 3, 117-125, (1992) · Zbl 0755.05075
[17] Steffen, E., Classifications and characterizations of snarks, Discrete math., 188, 183-203, (1998) · Zbl 0956.05089
[18] Steffen, E., On bicritical snarks, Math. slovaca, 51, 141-150, (2001) · Zbl 0985.05022
[19] Vizing, V.G., Ob ocenke chromatičeskogo klassa r-grafa, Diskr. analiz, 3, 25-30, (1964)
[20] J.J. Watkins, R.J. Wilson, A survey of snarks, Graph Theory, Combinatorics, and Applications, vol. 2, Wiley New York, 1991, pp. 1129-1144. · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.