Snarks fluxo-críticos

• Processo: 13/06137-8
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de junho de 2013
• Data de Término da vigência: 31 de maio de 2015
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Candida Nunes da Silva
• Beneficiário: Breno Lima de Freitas
• Instituição Sede: Centro de Ciências e Tecnologias para a Sustentabilidade (CCTS). Universidade Federal de São Carlos (UFSCAR). Sorocaba , SP, Brasil
• Assunto(s): Teoria dos grafos Sistemas hamiltonianos
• Palavra(s)-Chave do Pesquisador: Conjeturas de Tutte | fluxos inteiros | grafos fluxo-críticos | grafos hipohamiltonianos | snarks | Teoria dos Grafos

Resumo

O tema de pesquisa deste projeto são os grafos k-(aresta)-uxo-críticos, grafos que não admitem k-uxo, mas que após a contração de uma aresta qualquer passam a admitir um k-uxo. Dentre estes, nos concentraremos no estudo de snarks, que são grafos cúbicos que não admitem 3-coloração de arestas, e tampouco 4-uxo, dado que Tutte demonstrou que um grafo cúbico admite 3-coloração de arestas se e somente se admite 4-uxo. Diversas conjeturas famosas podem ser reduzidas a snarks, fato que motiva muito estudo da estrutura de tais grafos. A Conjetura dos 5-Fluxos de Tutte, a qual arma que todo grafo 2-aresta- conexo admite um 5-uxo é uma destas. Em trabalho recente, de 2013, Silva, Pesci e Lucchesi observaram que todo snark 4-uxo-crítico admite 5-uxo, e que os snarks não 4-uxo-críticos têm um snark 4-uxo-crítico como minor. Essa observação abre uma nova abordagem na tentativa de resolução da Conjetura dos 5-uxos de Tutte. Este pro jeto pretende iniciar a pesquisa segundo essa nova abordagem investigando para a classe dos snarks a existência de (I) alguma relação entre a propriedade de ser 4-uxo-crítico e ser hipohamiltoniano, isto é, não ter ciclo hamiltoniano mas passar a ter após a remoção de um vértice qualquer; ou (II) ser 4-uxo-crítico e ser bicrítico, isto é, não admitir 3-coloração de arestas, mas passar a admitir após a remoção de um par de vértices qualquer. (AU)