Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/9599| Type: | Dissertação |
| Title: | A conjectura de Tuza sobre triângulos em grafos |
| Title in English: | The conjecture of Tuza about triangles in graphs |
| Authors: | Freitas, Lucas Ismaily Bezerra |
| Advisor: | Lee, Orlando |
| Keywords: | Teoria dos Grafos;Empacotamento e cobertura combinatória;Conjectura de Tuza |
| Issue Date: | 2014 |
| Citation: | 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. |
| Abstract in Brazilian Portuguese: | 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. |
| Abstract: | 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. |
| URI: | http://www.repositorio.ufc.br/handle/riufc/9599 |
| Appears in Collections: | CQUIXADA - Dissertações defendidas em outras instituições |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2014_dis_libfreitas.pdf | 1,79 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.