| Texto completo | |
| Autor(es): |
Botler, F.
;
Fernandes, C. G.
;
Gutierrez, J.
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 13-pg., 2019-08-30. |
| Resumo | |
Tuza (1981) conjectured that the cardinality tau(G) of a minimum set of edges that intersects every triangle of a graph G is at most twice the cardinality nu(G) of a maximum set of edge-disjoint triangles of G. In this paper we present three results regarding Tuza's Conjecture. We verify it for graphs with treewidth at most 6; and we show that tau(G) <= 3/2 nu(G) for every planar triangulation G different from K-4; and that tau(G) <= 9/5 nu(G) + 1/5 if G is a maximal graph with treewidth 3. (AU) | |
| Processo FAPESP: | 15/08538-5 - Transversais em grafos |
| Beneficiário: | Juan Gabriel Gutierrez Alva |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |