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

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

doi:10.1016/j.endm.2017.06.065

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

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

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

Abstract

We prove that the maximum number of triangles in a C₅-free graph on n vertices is at most [Formula presented](1+o(1))n^3/2, improving an estimate of Alon and Shikhelman [Alon, N. and C. Shikhelman, Many T copies in H-free graphs. Journal of Combinatorial Theory, Series B 121 (2016) 146-172].

Original language	English (US)
Pages (from-to)	395-398
Number of pages	4
Journal	Electronic Notes in Discrete Mathematics
Volume	61
DOIs	https://doi.org/10.1016/j.endm.2017.06.065
State	Published - Aug 2017
Externally published	Yes

Keywords

Counting subgraphs
five cycle
H-free graphs
Triangles
Turán type

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Online availability

10.1016/j.endm.2017.06.065

Library availability

Discover UIUC Full Text

Cite this

@article{7ef2bcd5f63c40aa8d0a84eed0f8c1ac,

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 [Formula presented](1+o(1))n3/2, improving an estimate of Alon and Shikhelman [Alon, N. and C. Shikhelman, Many T copies in H-free graphs. Journal of Combinatorial Theory, Series B 121 (2016) 146-172].",

keywords = "Counting subgraphs, five cycle, H-free graphs, Triangles, Tur{\'a}n type",

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

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = aug,

doi = "10.1016/j.endm.2017.06.065",

language = "English (US)",

volume = "61",

pages = "395--398",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier BV",

}

TY - JOUR

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

AU - Ergemlidze, Beka

AU - Győri, Ervin

AU - Methuku, Abhishek

AU - Salia, Nika

PY - 2017/8

Y1 - 2017/8

N2 - We prove that the maximum number of triangles in a C5-free graph on n vertices is at most [Formula presented](1+o(1))n3/2, improving an estimate of Alon and Shikhelman [Alon, N. and C. Shikhelman, Many T copies in H-free graphs. Journal of Combinatorial Theory, Series B 121 (2016) 146-172].

AB - We prove that the maximum number of triangles in a C5-free graph on n vertices is at most [Formula presented](1+o(1))n3/2, improving an estimate of Alon and Shikhelman [Alon, N. and C. Shikhelman, Many T copies in H-free graphs. Journal of Combinatorial Theory, Series B 121 (2016) 146-172].

KW - Counting subgraphs

KW - five cycle

KW - H-free graphs

KW - Triangles

KW - Turán type

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

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

U2 - 10.1016/j.endm.2017.06.065

DO - 10.1016/j.endm.2017.06.065

M3 - Article

AN - SCOPUS:85026737901

SN - 1571-0653

VL - 61

SP - 395

EP - 398

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -