Premium
Triangles in C 5 ‐free graphs and hypergraphs of girth six
Author(s) -
Ergemlidze Beka,
Methuku Abhishek
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22723
Subject(s) - mathematics , combinatorics , girth (graph theory) , graph , discrete mathematics
We introduce a new approach and prove that the maximum number of triangles in a C 5 ‐free graph on n vertices is at most ( 1 + o ( 1 ) ) 1 3 2n 3 ∕ 2 .We show a connection to r ‐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‐ C 4 ‐free and C 5 ‐free graph.