Triangles in C5‐free graphs and hypergraphs of girth six

Beka Ergemlidze, Abhishek Methuku

Research output: Contribution to journalArticlepeer-review

77 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)26-39
JournalJournal of Graph Theory
Volume99
Issue number1
Early online date26 Jul 2021
DOIs
Publication statusE-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.

Cite this