Pentagons in triangle-free graphs

Thumbnail Image
Date
2018-12-01
Authors
Pfender, Florian
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

For all n≥9, we show that the only triangle-free graphs on n vertices maximizing the number 5-cycles are balanced blow-ups of a 5-cycle. This completely resolves a conjecture by Erd\H{o}s, and extends results by Grzesik and Hatami, Hladky, Kral, Norin and Razborov, where they independently showed this same result for large n and for all n divisible by 5.

Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
article
Comments

This is a manuscript of an article published as Lidický, Bernard, and Florian Pfender. "Pentagons in triangle-free graphs." European Journal of Combinatorics 74 (2018): 85-89. doi: 10.1016/j.ejc.2018.07.008. Posted with permission.

Rights Statement
Copyright
Mon Jan 01 00:00:00 UTC 2018
Funding
DOI
Supplemental Resources
Collections