Tuza's Conjecture is Asymptotically Tight for Dense Graphs. (14th March 2016)

• Record Type: Journal Article
• Authors: BARON, JACOB D.; KAHN, JEFF
• Is Part Of: Combinatorics, probability and computing. Volume 25:Number 5(2016:Sep.)
• Page Start: 645
• Page End: 667
• Publication Date: 2016-03-14
• Subjects: Primary 05C70, -- Secondary 05C50; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548316000067
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : An old conjecture of Z. Tuza says that for any graph G, the ratio of the minimum size, τ3 ( G ), of a set of edges meeting all triangles to the maximum size, ν3 ( G ), of an edge-disjoint triangle packing is at most 2. Here, disproving a conjecture of R. Yuster, we show that for any fixed, positive α there are arbitrarily large graphs G of positive density satisfying τ3 ( G ) > (1 − o (1))| G |/2 and ν3 ( G ) < (1 + α)| G |/4.