Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-22T17:06:10.068Z Has data issue: false hasContentIssue false

Tuza's Conjecture is Asymptotically Tight for Dense Graphs

Published online by Cambridge University Press:  14 March 2016

JACOB D. BARON
Affiliation:
Department of Mathematics, Rutgers University, Piscataway, NJ, USA (e-mail: [email protected], [email protected])
JEFF KAHN
Affiliation:
Department of Mathematics, Rutgers University, Piscataway, NJ, USA (e-mail: [email protected], [email protected])

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.

Type
Paper
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Alon, N. (1994) Explicit Ramsey graphs and orthonormal labelings. Electron. J. Combin. www.combinatorics.org/ojs/index.php/eljc/article/view/v1i1r12 CrossRefGoogle Scholar
[2] Alon, N. and Spencer, J. H. (2008) The Probabilistic Method, third edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley.CrossRefGoogle Scholar
[3] Bollobás, B. (1998) Modern Graph Theory, Vol. 184 of Graduate Texts in Mathematics, Springer.CrossRefGoogle Scholar
[4] Diestel, R. (2010) Graph Theory, fourth edition, Vol. 173 of Graduate Texts in Mathematics, Springer.CrossRefGoogle Scholar
[5] Gerke, S. and Steger, A. (2005) The sparse regularity lemma and its applications. In Surveys in Combinatorics 2005, Vol. 327 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 227258.CrossRefGoogle Scholar
[6] Haxell, P. (1999) Packing and covering triangles in graphs. Discrete Math. 195 251254.CrossRefGoogle Scholar
[7] Haxell, P. and Rödl, V. (2001) Integer and fractional packings in dense graphs. Combinatorica 21 1338.CrossRefGoogle Scholar
[8] Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley.CrossRefGoogle Scholar
[9] Kohayakawa, Y. (1997) Szemerédi's regularity lemma for sparse graphs. In Foundations of Computational Mathematics (Cucker, F. and Shub, M., eds), Springer, pp. 216230.CrossRefGoogle Scholar
[10] Krivelevich, M. (1995) On a conjecture of Tuza about packing and covering of triangles. Discrete Math. 142 281286.CrossRefGoogle Scholar
[11] Mantel, W. (1907) Problem 28. In Wiskundige Opgaven, Vol. 10, pp. 60–61.Google Scholar
[12] Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes: Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976, Vol. 260 of Colloques Internationaux du Centre National de la Recherche Scientifique, CNRS, pp. 399401.Google Scholar
[13] Turán, P. (1941) On an extremal problem in graph theory. Matematikai és Fizikai Lapok 48 436452.Google Scholar
[14] Tuza, Z. (1981) Conjecture. In Finite and Infinite Sets (Hajnal, A., Lovász, L. and Sós, V. T., eds), North-Holland.Google Scholar
[15] Yuster, R. (2012) Dense graphs with a large triangle cover have a large triangle packing. Combin. Probab. Comput. 21 952962.CrossRefGoogle Scholar