A note on the maximum number of triangles in a C5-free graph

Beka Ergemlidze; Abhishek Methuku; Nika Salia; Ervin Győri

doi:10.1002/jgt.22390

A note on the maximum number of triangles in a C₅-free graph

Beka Ergemlidze
, Abhishek Methuku
, Nika Salia
, Ervin Győri

Research output: Contribution to journal › Article › peer-review

Abstract

We prove that the maximum number of triangles in a C_5-free graph on n vertices is at most 1/2√2(1+0(1))n^3/2, improving an estimate of Alon and Shikhelman.

Original language	English (US)
Pages (from-to)	227-230
Number of pages	4
Journal	Journal of Graph Theory
Volume	90
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22390
State	Published - Mar 2019
Externally published	Yes

Keywords

extremal graphs
graphs
triangles

ASJC Scopus subject areas

Geometry and Topology

Online availability

10.1002/jgt.22390

Library availability

Discover UIUC Full Text

Cite this

@article{f4c80ab6778a49618e4cde086ca0a370,

title = "A note on the maximum number of triangles in a C5-free graph",

abstract = "We prove that the maximum number of triangles in a C5-free graph on n vertices is at most 1/2√2(1+0(1))n3/2, improving an estimate of Alon and Shikhelman.",

keywords = "extremal graphs, graphs, triangles",

author = "Beka Ergemlidze and Abhishek Methuku and Nika Salia and Ervin Gy{\H o}ri",

note = "The research of the second and third authors is partially supported by the National Research, Development and Innovation Office NKFIH, grant K116769 and SNN 117879.",

year = "2019",

month = mar,

doi = "10.1002/jgt.22390",

language = "English (US)",

volume = "90",

pages = "227--230",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - A note on the maximum number of triangles in a C5-free graph

AU - Ergemlidze, Beka

AU - Methuku, Abhishek

AU - Salia, Nika

AU - Győri, Ervin

N1 - The research of the second and third authors is partially supported by the National Research, Development and Innovation Office NKFIH, grant K116769 and SNN 117879.

PY - 2019/3

Y1 - 2019/3

N2 - We prove that the maximum number of triangles in a C5-free graph on n vertices is at most 1/2√2(1+0(1))n3/2, improving an estimate of Alon and Shikhelman.

AB - We prove that the maximum number of triangles in a C5-free graph on n vertices is at most 1/2√2(1+0(1))n3/2, improving an estimate of Alon and Shikhelman.

KW - extremal graphs

KW - graphs

KW - triangles

UR - https://www.scopus.com/pages/publications/85053670621

UR - https://www.scopus.com/pages/publications/85053670621#tab=citedBy

U2 - 10.1002/jgt.22390

DO - 10.1002/jgt.22390

M3 - Article

AN - SCOPUS:85053670621

SN - 0364-9024

VL - 90

SP - 227

EP - 230

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -