A Study of Critical Snarks

• Breno de Freitas UFSCar
• Cândida da Silva UFSCar
• Cláudio Lucchesi UFMS

Abstract

Snarks are cubic graphs that do not admit a 3-edge-colouring and that are regarded to be the minimal cubic graphs without this property. Snarks have been studied by many researchers throughout the history, since many famous open problems are known to have their potential counter-examples residing in this family of graphs. In this paper we present relations between several classes of critical snarks. It follows from one of such relations that no hypohamiltonian snark is a counter-example to Tutte’s 5-flow Conjecture, thus giving a positive answer to a question proposed by Cavicchioli et al. in 2003.

References

Bondy, J. A. and Murty, U. S. R. (1976). Graph Theory with Applications. Elsevier North Holland.

Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Springer.

Brinkmann, G., Goedgebeur, J., Hägglund, J., and Markstrom, K. (2013). Generation and properties of snarks. J. Comb. Theory, Series B, 103(4):468– 488. Preliminary version available at http://arxiv.org/abs/1206.6690.

Cavicchioli, A.,Murgolo, T. E., Ruini, B., and Spaggiari, F. (2003). Special classes of snarks. Acta Applicandae Mathematica, 76:57–88.

Chetwynd, A. G. and Wilson, R. J. (1981). Snarks and Supersnarks. In Alavi, Y., Chartrand, G., Goldsmith, D. L., Lesniak-Foster, L., and Lick, D. R., editors, The Theory and Applications of Graphs, pages 215–241. Wiley.

da Silva, C. N. and Lucchesi, C. L. (2007). Flow-critical graphs. Technical report, Instituto de Computac¸ ˜ao, UNICAMP, Brasil.

da Silva, C. N. and Lucchesi, C. L. (2008). Flow-critical graphs. Electronic Notes in Discrete Mathematics, 30:165–170.

da Silva, C. N. and Lucchesi, C. L. (2012). Flower-snarks are flow-critical. Available at http://www.dcomp.sor.ufscar.br/candida/ publications.

da Silva, C. N., Pesci, L., and Lucchesi, C. L. (2013). Snarks and flow-critical graphs. Electronic Notes in Discrete Mathematics, 44:299–305.

de Almeida e Silva, L. M. (1991). Fluxos inteiros em grafos. Master’s thesis, Departamento de Ciˆencia da Computac¸ ˜ao - UNICAMP. Em portuguˆes.

Diestel, R. (1996). Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag.

Fiorini, S. (1983). Hypohamiltonian snarks. Graphs and other combinatorial topics, Proc. 3rd Czech. Symp., Prague 1982, Teubner-Texte Math. 59, 70-75 (1983).

Fulkerson, D. (1971). Blocking and anti-blocking pairs of polyhedra. Math. Programming 1, 69:168–194.

Gardner, M. (1976). Matematical games: Snarks, boojums and other conjectures related to the four-color-map theorem. Scientific American, 234:126–130.

Isaacs, R. (1975). Infinite families of non-trivial trivalent graphs which are not tait colorable. Amer. Math. Monthly, 82:221–239.

Jaeger, F. (1988). Nowhere-zero flow problems. volume 3 of Selected Topics in Graph Theory, pages 71–95. Academic Press.

Nedela, R. and Skoviera, M. (1996). Decompositions and reductions of snarks. Journal of Graph Theory, 22:253–279.

Seymour, P. D. (1979). Sums of circuits. Graph theory and related topics, 1:341–355.

Seymour, P. D. (1981). Nowhere-zero 6-flows. J. Comb. Theory, Series B, 30:130–135.

Seymour, P. D. (1995). Nowhere-zero flows. In Graham, R. L. and M. Grötschel, L. L., editors, Handbook of Combinatorics, chapter 4, pages 289–299. Elsevier.

Steffen, E. (1998). Classifications and characterizations of snarks. Discrete Mathematics, 188:183–203.

Steffen, E. (1999). Non-bicritical critical snarks. Graphs Comb., 15:473– 480.

Szekeres, G. (1973). Polyhedral decompositions of cubic graphs. Bull. Austral. Math. Soc., 8:367 – 387.

Tutte, W. T. (1954). A contribution to the theory of chromatic polynomials. Can. J. Math., 6:80–91.

West, D. B. (1996). Introduction to Graph Theory. Prentice Hall.

Younger, D. H. (1983). Integer flows. Journal of Graph Theory, 7:349–357.

Zhang, C.-Q. (1997). Integer Flows and Cycle Covers of Graphs. Marcel Dekker.