TY - JOUR

T1 - Multi-transversals for Triangles and the Tuza’s Conjecture

AU - Chalermsook, Parinya

AU - Khuller, Samir

AU - Sukprasert, Pattara

AU - Uniyal, Sumedha

N1 - Publisher Copyright:
Copyright © 2020, The Authors. All rights reserved.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/1/1

Y1 - 2020/1/1

N2 - In this paper, we study a primal and dual relationship about triangles: For any graph G, let ν(G) be the maximum number of edge-disjoint triangles in G, and τ(G) be the minimum subset F of edges such that G \ F is triangle-free. It is easy to see that ν(G) ≤ τ(G) ≤ 3ν(G), and in fact, this rather obvious inequality holds for a much more general primal-dual relation between k-hyper matching and covering in hypergraphs. Tuza conjectured in 1981 that τ(G) ≤ 2ν(G), and this question has received attention from various groups of researchers in discrete mathematics, settling various special cases such as planar graphs and generalized to bounded maximum average degree graphs, some cases of minor-free graphs, and very dense graphs. Despite these efforts, the conjecture in general graphs has remained wide open for almost four decades. In this paper, we provide a proof of a non-trivial consequence of the conjecture; that is, for every k ≥ 2, there exist a (multi)-set F ⊆ E(G): |F| ≤ 2kν(G) such that each triangle in G overlaps at least k elements in F. Our result can be seen as a strengthened statement of Krivelevich’s result on the fractional version of Tuza’s conjecture (and we give some examples illustrating this.) The main technical ingredient of our result is a charging argument, that locally identifies edges in F based on a local view of the packing solution. This idea might be useful in further studying the primal-dual relations in general and the Tuza’s conjecture in particular.

AB - In this paper, we study a primal and dual relationship about triangles: For any graph G, let ν(G) be the maximum number of edge-disjoint triangles in G, and τ(G) be the minimum subset F of edges such that G \ F is triangle-free. It is easy to see that ν(G) ≤ τ(G) ≤ 3ν(G), and in fact, this rather obvious inequality holds for a much more general primal-dual relation between k-hyper matching and covering in hypergraphs. Tuza conjectured in 1981 that τ(G) ≤ 2ν(G), and this question has received attention from various groups of researchers in discrete mathematics, settling various special cases such as planar graphs and generalized to bounded maximum average degree graphs, some cases of minor-free graphs, and very dense graphs. Despite these efforts, the conjecture in general graphs has remained wide open for almost four decades. In this paper, we provide a proof of a non-trivial consequence of the conjecture; that is, for every k ≥ 2, there exist a (multi)-set F ⊆ E(G): |F| ≤ 2kν(G) such that each triangle in G overlaps at least k elements in F. Our result can be seen as a strengthened statement of Krivelevich’s result on the fractional version of Tuza’s conjecture (and we give some examples illustrating this.) The main technical ingredient of our result is a charging argument, that locally identifies edges in F based on a local view of the packing solution. This idea might be useful in further studying the primal-dual relations in general and the Tuza’s conjecture in particular.

UR - http://www.scopus.com/inward/record.url?scp=85094382557&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85094382557&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85094382557

JO - Free Radical Biology and Medicine

JF - Free Radical Biology and Medicine

SN - 0891-5849

ER -