×

A note on 3-partite graphs without 4-cycles. (English) Zbl 1536.05203

Summary: Let \(C_4\) be a cycle of order 4. Write \(\operatorname{ex}(n,n,n, C_4)\) for the maximum number of edges in a balanced 3-partite graph whose vertex set consists of three parts, each has \(n\) vertices that have no subgraph isomorphic to \(C_4\). In this paper, we show that \(\operatorname{ex}(n,n,n, C_4) \geq \frac{3}{2} n(p + 1)\), where \(n = \frac{p(p - 1)}{2}\) and \(p\) is a prime number. Note that \(\operatorname{ex}(n, n, n, C_4) \leq (\frac{3\sqrt{2}}{2}+ o (1)) n^{\frac{3}{2}}\) from M. Tait and C. Timmons works [J. Comb. Des. 27, No. 6, 391–405 (2019; Zbl 1479.05171)]. Since for every integer \(m\), one can find a prime \(p\) such that \(m \leq p \leq (1+ o(1))m\), we obtain that \(\lim\limits_{n \to \infty} \frac{ex(n,n,n, C_4)}{\frac{3\sqrt{2}}{2} n^{\frac{3}{2}}} = 1\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C38 Paths and cycles

Citations:

Zbl 1479.05171
Full Text: DOI

References:

[1] B.Bollobás, Extremal graph theory, Academic Press Inc. (London) Ltd., New York, 1978. · Zbl 0419.05031
[2] W. G.Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull.9 (1966), 281-285. · Zbl 0178.27302
[3] C. R. J.Clapham, A.Flockhart, and J.Sheehan, Graphs without four‐cycles, J. Graph Theory13 (1989), no. 1, 29-47. · Zbl 0679.05043
[4] P.Erdös, On sequences of integers no one of which dives the product of two others and some related problems, Mitt. Forsch.‐Ins. Math. Mech. Univ. Tomsk2 (1938), 74-82. · Zbl 0020.00504
[5] P.Erdös and A.Rényi, On a problem in the theory of graphs, (Hungarian) Magyar Tud. Akad. Mat. Kutat0́ Int. Közl.7 (1962), 623-641.
[6] P.Erdös, A.Rényi, and V. T.Sós, On a problem of graph theory, Studia Sci. Math. Hungar.1 (1966), 215-235. · Zbl 0144.23302
[7] Z.Füredi, On the number of edges of quadrilateral‐free graphs, J. Combin. Theory Ser. B68 (1996), 1-6. · Zbl 0858.05063
[8] Z.Füredi, New asymptotics for bipartite Turán numbers, J. Combin. Theory Ser. A75 (1996), no. 1, 141-144. · Zbl 0858.05064
[9] T.Kövári, V. T.Sós, and P.Turán, On a problem of K. Zarankiewicz, Colloq. Math.3 (1954), 50-57. · Zbl 0055.00704
[10] D.Mubayi and J.Williford, On the independence number of the Erdös‐Rényi and projective norm graphs and a related hypergraph, J. Graph Theory56 (2007), no. 2, 113-127. · Zbl 1128.05040
[11] P.Rowlinson and Y.Yang, On extremal graphs without four‐cycles, Util. Math.41 (1992), 204-210. · Zbl 0768.05059
[12] M.Tait and C.Timmons, The Zarankiewicz problem in 3‐partite graphs, J. Combin. Des.27 (2019), 391-405. · Zbl 1479.05171
[13] K.Zarankiewicz, Problem 101, Colloq. Math.2 (1951), 301.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.