Hatami, Hamed, Hladký, Jan, Králʼ, Daniel, Norine, Serguei and Razborov, Alexander (2013) On the number of pentagons in triangle-free graphs. Journal of Combinatorial Theory, Series A, Volume 120 (Number 3). pp. 722-732. doi:10.1016/j.jcta.2012.12.008

Preview

Text WRAP_Kral_Number.pdf - Accepted Version Download (429Kb) | Preview

Request Changes to record.

Abstract

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.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Computer Science Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH):	Graph theory
Journal or Publication Title:	Journal of Combinatorial Theory, Series A
Publisher:	Elsevier BV
ISSN:	0097-3165
Official Date:	April 2013
Dates:	Date Event April 2013 Published
Volume:	Volume 120
Number:	Number 3
Page Range:	pp. 722-732
DOI:	10.1016/j.jcta.2012.12.008
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	Engineering and Physical Sciences Research Council (EPSRC), European Research Council (ERC), Seventh Framework Programme (European Commission) (FP7), Rossiĭskiĭ fond fundamentalʹnykh issledovaniĭ [Russian Foundation for Basic Research] (RFBR), Toyota Kōgyō Daigaku [Toyota Technological Institute]
Grant number:	EP/D063191/1 (EPSRC) ; 259385 (ERC)

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads