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

Submitted by Milena Rubi (milenarubi@ufscar.br) on 2016-10-19T12:46:24Z No. of bitstreams: 1 CARNEIRO_Andre_2016.pdf: 645256 bytes, checksum: 6bb0b1eafe6943542ba50b6e8987f5df (MD5)
Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2016-10-19T12:46:37Z (GMT) No. of bitstreams: 1 CARNEIRO_Andre_2016.pdf: 645256 bytes, checksum: 6bb0b1eafe6943542ba50b6e8987f5df (MD5)
Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2016-10-19T12:46:48Z (GMT) No. of bitstreams: 1 CARNEIRO_Andre_2016.pdf: 645256 bytes, checksum: 6bb0b1eafe6943542ba50b6e8987f5df (MD5)
Made available in DSpace on 2016-10-19T12:46:57Z (GMT). No. of bitstreams: 1 CARNEIRO_Andre_2016.pdf: 645256 bytes, checksum: 6bb0b1eafe6943542ba50b6e8987f5df (MD5) Previous issue date: 2016-04-29
Não recebi financiamento
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.
O tema de pesquisa deste projeto são os grafos k-fluxo-críticos, grafos que não admitem k-fluxo, mas que após a contração de um par de vértices, adjacentes ou não, passam a admitir um k-fluxo. 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-fluxo, dado que Tutte demonstrou que um grafo cúbico admite 3-coloração de arestas se e somente se admite 4-fluxo. Diversas conjecturas famosas podem ser reduzidas a snarks, fato que motiva muito estudo da estrutura de tais grafos. A Conjectura dos 5-Fluxos de Tutte, a qual afirma que todo grafo 2-aresta-conexo admite um 5-fluxo é uma destas. Em 2013, Brinkmann, Goedgebeur, Hägglund e Markström conseguiram gerar computacionalmente todos os snarks com até 36 vértices. Silva, Pesci e Lucchesi observaram que todo snark 4-fluxo-crítico admite 5-fluxo, e que os snarks não 4-fluxo-críticos têm um snark 4-fluxocrítico como minor. Essa observação abre uma nova abordagem na tentativa de resolução da Conjectura dos 5-fluxos de Tutte. Este trabalho é um início de pesquisa segundo essa nova abordagem buscando identificar entre os snarks de até 36 vértices quais são os snarks 4-fluxo-críticos.