J 2013

On the number of pentagons in triangle-free graphs

HATAMI, H; J HLADKY; Daniel KRÁĽ; S NORINE; A RAZBOROV et al.

Základní údaje

Originální název

On the number of pentagons in triangle-free graphs

Autoři

HATAMI, H; J HLADKY; Daniel KRÁĽ; S NORINE a A RAZBOROV

Vydání

Journal of Combinatorial Theory, Series A, SAN DIEGO, ACADEMIC PRESS INC ELSEVIER SCIENCE, 2013, 0097-3165

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.868

Označené pro přenos do RIV

Ne

DOI

UT WoS

Klíčová slova anglicky

Pentagon density; Triangle-free graphs; Extremal graph theory
Změněno: 6. 11. 2020 08:57, Mgr. Darina Boukalová

Anotace

V originále

Using the formalism of flag algebras, we prove that every triangle-free graph G with n vertices contains at most (n/5)(5) cycles of length five. Moreover, the equality is attained only when n is divisible by five and G is the balanced blow-up of the pentagon. We also compute the maximal number of pentagons and characterize extremal graphs in the non-divisible case provided n is sufficiently large. This settles a conjecture made by Erdos in 1984. (C) 2012 Elsevier Inc. All rights reserved.