Projects per year
Abstract
We introduce a new approach and prove that the maximum number of triangles in a 𝐶5 -free graph on 𝑛 vertices is at most
(1+𝑜(1))132⎯⎯√𝑛3∕2.
We show a connection to 𝑟 -uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced- 𝐶4 -free and 𝐶5 -free graph.
(1+𝑜(1))132⎯⎯√𝑛3∕2.
We show a connection to 𝑟 -uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced- 𝐶4 -free and 𝐶5 -free graph.
Original language | English |
---|---|
Pages (from-to) | 26-39 |
Journal | Journal of Graph Theory |
Volume | 99 |
Issue number | 1 |
Early online date | 26 Jul 2021 |
DOIs | |
Publication status | E-pub ahead of print - 26 Jul 2021 |
Keywords
- Berge hypergraphs
- generalized Turán
- triangles
Fingerprint
Dive into the research topics of 'Triangles in C5‐free graphs and hypergraphs of girth six'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Approximate Structure in Large Graphs and Hypergraphs
Engineering & Physical Science Research Council
1/01/19 → 31/12/21
Project: Research Councils