On Tuza's conjecture for triangulations and graphs with small treewidth

Autor(es)

Botler, Fabio ^[1] ; Fernandes, Cristina G. ^[2] ; Gutierrez, Juan ^[3]

Afiliação do(s) autor(es)

^[1] Univ Fed Rio de Janeiro, Programa Engn Sistemas & Comp, COPPE, Rio De Janeiro - Brazil

^[2] Univ Sao Paulo, Dept Ciencia Comp, Sao Paulo - Brazil

^[3] Univ Ingn & Tecnol UTEC, Dept Ciencia Comp, Barranco - Peru

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 344, n. 4 APR 2021.
• Citações Web of Science: 0

Resumo

Tuza (1981) conjectured that the size tau(G) of a minimum set of edges that intersects every triangle of a graph G is at most twice the size 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; 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. Our first result strengthens a result of Tuza, implying that tau(G) <= 2 nu(G) for every K-8-free chordal graph G. (C) 2020 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 15/08538-5 - Transversais em grafos
• Beneficiário: Juan Gabriel Gutierrez Alva
• Modalidade de apoio: Bolsas no Brasil - Doutorado