dc.contributor.author | 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.citation | CARNEIRO, André Breda. Identificação dos snarks fluxo-críticos de ordem pequena. 2016. Dissertação (Mestrado em Ciência da Computação) – Universidade Federal de São Carlos, Sorocaba, 2016. Disponível em: https://repositorio.ufscar.br/handle/ufscar/7920. | * |
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.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 - PPGCC-So | 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 |
dc.contributor.authorlattes | http://lattes.cnpq.br/6595362919175589 | por |