The Library
On the number of pentagons in triangle-free graphs
Tools
Tools
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
