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

• Fábio Botler Universidad de Valparaíso
• Cristina G. Fernandes USP
• Juan Gutiérrez USP

DOI: https://doi.org/10.5753/etc.2018.3141

Abstract

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.

References

Bodlaender, H. (1998). A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1):1–45.

Gross, J. (2014). Embeddings of graphs of fixed treewidth and bounded degree. ARS Mathematica Contemporanea, 7:379–403.

Haxell, P. E. and Kohayakawa, Y. (1998). Packing and covering triangles in tripartite graphs. Graphs and Combinatorics, 14(1):1–10.

Puleo, G. (2015). Tuza’s conjecture for graphs with maximum average degree less than 7. European Journal of Combinatorics, 49:134–152.

Tuza, Z. (1981). Conjecture in: finite and infinite sets. In Proc. Colloq. Math. Soc. J. Bolyai (Eger, Hungary, 1981), volume 37, page 888.

Tuza, Z. (1990). A conjecture on triangles of graphs. Graphs and Combinatorics, 6(4):373–380.