Density of balanced 3-partite graphs without 3-cycles or 4-cycles. (English) Zbl 1506.05075
Summary: Let \(C_k\) be a cycle of order \(k\), where \(k\geqslant 3\). Let \(\mathrm{ex}(n, n, n, \{C_3, C_4\})\) be the maximum number of edges in a balanced \(3\)-partite graph whose vertex set consists of three parts, each has \(n\) vertices that has no subgraph isomorphic to \(C_3\) or \(C_4\). We construct dense balanced 3-partite graphs without 3-cycles or 4-cycles and show that \(\mathrm{ex}(n, n, n, \{C_3, C_4\})\geqslant (\frac{6\sqrt{2}-8}{(\sqrt{2}-1)^{3/2}}+o(1))n^{3/2}\).
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C35 | Extremal problems in graph theory |
| 05C38 | Paths and cycles |
| 05C42 | Density (toughness, etc.) |
| 05C75 | Structural characterization of families of graphs |
| 05A15 | Exact enumeration problems, generating functions |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
Keywords:
balanced 3-partite graphReferences:
| [1] | P. Allen, P. Keevash, B. Sudakov, and J. Verstra¨ete. Tur´an numbers of bipartite graphs plus an odd cycles.J. Combinatorial Theory, Ser. B, 106:134-162, 2014. · Zbl 1297.05124 |
| [2] | R. C. Baker, G. Harman, and J. Pintz. The difference between consecutive primes, II.Proc. Lond. Math. Soc., 83(3): 532-562, 2001. · Zbl 1016.11037 |
| [3] | R. D. Dutton and R. C. Brigham. Edges in graphs with large girth.Graphs Combin., 7: 315-321, 1991. · Zbl 0755.05048 |
| [4] | P. Erd˝os. On sequences of integers no one of which dives the product of two others and some related problems.Mitt. Forsch.-Ins. Math. Mech. Univ. Tomsk, 2:74-82, 1938. · Zbl 0020.00504 |
| [5] | P. Erd˝os. Some recent progress on extremal problems in graph theory.Congr. Numerantium, 14:3-14, 1975. · Zbl 0323.05126 |
| [6] | D. K. Garnick, Y. H. H. Kwong, and F. Lazebnik. Extremal graphs without threecycles or four-cycles.J. Graph Theory, 17:633-645, 1993. · Zbl 0784.05033 |
| [7] | D. K. Garnick and N. A. Nieuwejaar. Non-isomorphic extremal graphs without threecycles and four-cycles.J. Combin. Math. Combin. Comput., 12:33-56, 1992. · Zbl 0773.05064 |
| [8] | T. K˝ov´ari, V. T. S´os, and P. Tur´an. On a problem of K. Zarankiewicz.Colloq. Math., 3:50-57, 1954. · Zbl 0055.00704 |
| [9] | F. Lazebnik and A. J. Woldar. General properties of some families of graphs defined by systems of equations.J. Graph Theory, 38:65-86, 2001. · Zbl 0990.05080 |
| [10] | Z. Lv, M. Lu, and C. Fang. A note on 3-partite graphs without 4-cycles.J. of Comb. Designs, 28:753-757, 2020. · Zbl 1536.05203 |
| [11] | D. Mubayi and J. Williford. On the independence number of the Erd˝os-R´enyi and projective norm graphs and a related hypergraph.J. Graph Theory, 56(2):113-127, 2007. · Zbl 1128.05040 |
| [12] | M. Tait and C. Timmons. The Zarankiewicz problem in 3-partite graphs.J. of Comb. Designs, 27:391-405, 2019. · Zbl 1479.05171 |
| [13] | R. Wenger. Extremal graphs with noC4′s,C6′s, orC10′s.J. Combinatorial Theory, Ser. B, 52:113-116, 1991 · Zbl 0755.05060 |
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.
