
The Library
On the number of pentagons in triangle-free graphs
Tools
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 ISSN 0097-3165.
|
Text
WRAP_Kral_Number.pdf - Accepted Version Download (429Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.jcta.2012.12.008
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, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > 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: |
|
||||
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 | ||||
Date of first compliant deposit: | 25 December 2015 | ||||
Date of first compliant Open Access: | 25 December 2015 | ||||
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
Downloads per month over past year