A Study of Critical Snarks
Resumo
Snarks são grafos cúbicos que não admitem 3-coloração de arestas e que são considerados os grafos cúbicos minimais sem esta propriedade. Snarks vêm sendo estudados por vários pesquisadores no decorrer da história, uma vez que é sabido que vários problemas abertos famosos devem ter seus potenciais contra-exemplos dentro desta família de grafos. Neste artigo apresentamos relações entre várias classes de snarks críticos. é consequência de uma destas relações que nenhum snark hipohamiltoniano é um contra-exemplo para a Conjectura dos 5-fluxos de Tutte. Essa asserção responde afirmativamente a uma questão proposta por Cavicchioli et al. em 2003.
Referências
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.
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.
Publicado
20/07/2015
Como Citar
DE FREITAS, Breno; DA SILVA, Cândida; LUCCHESI, Cláudio.
A Study of Critical Snarks. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 34. , 2015, Recife.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 21-30.
