Show simple item record

dc.creatorCarneiro, André Breda
dc.date.accessioned2016-10-19T12:46:57Z
dc.date.available2016-10-19T12:46:57Z
dc.date.issued2016-04-29
dc.identifier.urihttps://repositorio.ufscar.br/handle/ufscar/7920
dc.description.abstractThe 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.sponsorshipNão recebi financiamentopor
dc.language.isoporpor
dc.publisherUniversidade Federal de São Carlospor
dc.rights.uriAcesso abertopor
dc.subjectTeoria dos grafospor
dc.subjectGraph theoryeng
dc.subjectSnarkpor
dc.subjectConjectura dos 5-Fluxospor
dc.subjectk-fluxo-críticopor
dc.subject5-flow conjectureeng
dc.subjectk-flow-criticaleng
dc.titleIdentificação dos snarks fluxo-críticos de ordem pequenapor
dc.title.alternativeIdentification of flow-critical snarks of small ordereng
dc.typeDissertaçãopor
dc.contributor.advisor1Silva, Cândida Nunes da
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/6019111128413167por
dc.creator.Latteshttp://lattes.cnpq.br/6595362919175589por
dc.description.resumoO 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.initialsUFSCarpor
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (Campus SOROCABA)por
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::MATEMATICA DA COMPUTACAOpor
dc.ufscar.embargoOnlinepor
dc.publisher.addressCâmpus Sorocabapor


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record