Freitas, L. I. B. A conjectura de Tuza sobre triângulos em grafos. 2014. 83 f. Dissertação (Mestrado Ciência da Computação) - Instituto de Computação, Universidade Estadual de Campinas, Campinas, 2014. / Submitted by Juliana Almeida (julianaufc@gmail.com) on 2014-10-30T18:26:55Z
No. of bitstreams: 1
2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5) / Approved for entry into archive by Juliana Almeida(julianaufc@gmail.com) on 2014-10-30T18:28:27Z (GMT) No. of bitstreams: 1
2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5) / Made available in DSpace on 2014-10-30T18:28:27Z (GMT). No. of bitstreams: 1
2014_dis_libfreitas.pdf: 1836193 bytes, checksum: 8a654f1e68aa87973b4560f5c194508f (MD5)
Previous issue date: 2014 / In this thesis we study the conjecture of Tuza, which relates covering of triangles (by edges) with packing of edge-disjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edge-disjoint triangles is at most twice the size of a minimum cover of
triangles by edges. The general case of the conjecture remains open. However, several attempts to prove it appeared in the literature, which contain results for several classes of graphs. In this thesis, we present the main known results for the conjecture of Tuza. Currently, there are several versions of Tuza’s conjecture. Nevertheless, we emphasize that our focus is on conjecture applied to simple graphs. We also present a conjecture that, if verified, implies the validity of the conjecture of Tuza. We also show that if G is a mininum counterexample to the conjecture of Tuza, then G is 4-connected. We can deduce from this result that the conjecture of Tuza is
valid for graphs with no K5 minor. / Neste trabalho estudamos a conjectura de Tuza, que relaciona cobertura mínima de triângulos por arestas com empacotamento máximo de triângulos aresta-disjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos aresta-disjuntos é no máximo duas vezes o tamanho de uma cobertura mínima de triângulos por arestas. O caso
geral da conjectura continua aberta. Contudo, diversas tentativas de prová-la surgiram na literatura,
obtendo resultados para várias classes de grafos. Nesta dissertação¸ nós apresentamos
os principais resultados obtidos da conjectura de Tuza. Atualmente, existem várias versões da conjectura. Contudo, ressaltamos que nosso foco está na conjectura aplicada a grafos simples.
Apresentamos também uma conjectura que se verificada, implica na veracidade da conjectura de Tuza. Demonstramos ainda que se G é um contraexemplo mínimo para a conjectura de Tuza, então G é 4-conexo. Deduzimos desse resultado que a conjectura de Tuza é válida para grafos sem minor do K5.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.repositorio.ufc.br:riufc/9599 |
| Date | January 2014 |
| Creators | Freitas, Lucas Ismaily Bezerra |
| Contributors | Lee, Orlando |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds