Identificação dos snarks fluxo-críticos de ordem pequena

• Ano de defesa: 2016
• Autor(a) principal: Carneiro, André Breda
• Orientador(a): Silva, Cândida Nunes da
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de São Carlos; Câmpus Sorocaba
• Programa de Pós-Graduação: Programa de Pós-Graduação em Ciência da Computação - PPGCC-So
• Palavras-chave em Português: Teoria dos grafos; Snark; Conjectura dos 5-Fluxos; k-fluxo-crítico
• Palavras-chave em Inglês: Graph theory; 5-flow conjecture; k-flow-critical
• Área do conhecimento CNPq: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::MATEMATICA DA COMPUTACAO
• Link de acesso: https://repositorio.ufscar.br/handle/20.500.14289/7920

The main theme of this dissertation are the k-flow-critical graphs, which are graphs that do not have a k-flow but once any two vertices (either adjacent or not) are identified the smaller graph thus obtained has a k-flow. Amongst those, we focused our study on snarks, which are cubic graphs that do not have a 3-edge-coloring, nor a 4-flow, as Tutte showed that a cubic graph has a 3-edge-coloring if and only if it has a 4-flow. Several famous conjectures can be reduced to snarks, and such fact motivates the study of the structure of such graphs. The 5-Flow Conjecture of Tutte, which states that every 2-edgeconnected graph has a 5-flow is one of them. In 2013, Brinkmann, Goedgebeur, Hägglund and Markström generated all snarks of order at most 36. Silva, Pesci and Lucchesi observed that every 4-flow-critical snark has a 5-flow and that every non-4-flow-critical snark has a 4-flow-critical snark as a minor. This observation allows a new approach to try to resolve Tutte’s 5-Flow Conjecture. This work is an attempt to start following this new approach by identifying which snarks of order at most 36 are 4-flow-critical.