Seminário de Teoria da Computação

                 O Perfume dos Flower-Snarks

                     Cândida Nunes da Silva

             Sexta-feira, 12 de dezembro de 2008
                     Sala 322  16:00hs


Snarks são grafos cúbicos sem aresta de corte e que não admitem
3-coloração de suas arestas. O primeiro snark foi descoberto por
Petersen em 1898 e, em sua homenagem, recebeu seu nome, é o famoso
grafo de Petersen. Alguns outros exemplos de snarks foram descobertos
nos anos subsequentes. A pequena quantidade de tais exemplos e a
dificuldade de generalização deram a impressão de serem estes grafos
raros. Essa raridade aparente inspirou Blanche Descartes (1948) a
chamá-los de snarks em alusão ao poema de Lewis Carrol "The Hunting of
the Snark" que narra a busca a um snark, uma criatura sem descrição
física, mas temível e difícil de encontrar. Finalmente em 1975, Isaacs
descobriu os flower-snarks, uma família infinita de snarks, com regra
de construção bastante simples. Nesta palestra falaremos sobre os
flower-snarks e algumas características estruturais que fazem com que
estes não admitam uma 3-coloração de arestas. O charme e a
simplicidade de tais propriedades estruturais podem ser interpretados
como sendo parte do "perfume" dos flower-snarks.