dc.creator Carneiro, André Breda dc.date.accessioned 2016-10-19T12:46:57Z dc.date.available 2016-10-19T12:46:57Z dc.date.issued 2016-04-29 dc.identifier.uri https://repositorio.ufscar.br/handle/ufscar/7920 dc.description.abstract 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. eng dc.description.sponsorship Não recebi financiamento por dc.language.iso por por dc.publisher Universidade Federal de São Carlos por dc.rights.uri Acesso aberto por dc.subject Teoria dos grafos por dc.subject Graph theory eng dc.subject Snark por dc.subject Conjectura dos 5-Fluxos por dc.subject k-fluxo-crítico por dc.subject 5-flow conjecture eng dc.subject k-flow-critical eng dc.title Identificação dos snarks fluxo-críticos de ordem pequena por dc.title.alternative Identification of flow-critical snarks of small order eng dc.type Dissertação por dc.contributor.advisor1 Silva, Cândida Nunes da dc.contributor.advisor1Lattes http://lattes.cnpq.br/6019111128413167 por dc.creator.Lattes http://lattes.cnpq.br/6595362919175589 por dc.description.resumo 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. por dc.publisher.initials UFSCar por dc.publisher.program Programa de Pós-graduação em Ciência da Computação (Campus SOROCABA) por dc.subject.cnpq CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::MATEMATICA DA COMPUTACAO por dc.ufscar.embargo Online por dc.publisher.address Câmpus Sorocaba por
﻿