On Tuza's conjecture for graphs with treewidth at most 6

  • Fábio Botler
  • Cristina G. Fernandes
  • Juan Gutiérrez

Resumo


Tuza (1981) conjectured that the size τ (G) of a minimum set of edges that meets every triangle of a graph G is at most twice the size ν(G) of a maximum set of edge-disjoint triangles of G. In this paper we verify this conjecture for graphs with treewidth at most 6. In this paper, all graphs considered are simple and the notation and terminology are standard. A triangle transversal of a graph G is a set of edges of G whose deletion results in a triangle-free graph; and a triangle packing of G is a set of edge-disjoint triangles of G. We denote by τ (G) (resp. ν(G)) the size of a minimum triangle transversal (resp. triangle packing) of G. In [Tuza 1981] the following conjecture was posed: Conjecture (Tuza, 1981). For every graph G, we have τ (G) ≤ 2ν(G).

Publicado
26/07/2018
BOTLER, Fábio; FERNANDES, Cristina G.; GUTIÉRREZ, Juan. On Tuza's conjecture for graphs with treewidth at most 6. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3141.