The maximum number of induced C₅'s in a planar graph

2020/04/02 by Ghosh, Debarun, Győri, Ervin, Janzer, Oliver +3
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2004.01162

Abstract

Finding the maximum number of induced cycles of length k in a graph on n vertices has been one of the most intriguing open problems of Extremal Graph Theory. Recently Balogh, Hu, Lidický and Pfender answered the question in the case k=5. In this paper we determine precisely, for all sufficiently large n, the maximum number of induced 5-cycles that an n-vertex planar graph can contain.

Related

• Planar graphs with the maximum number of induced 4-cycles or 5-cycles
• On the number of cycles of length k in a maximal planar graph
• Counting k-cycles in 5-connected planar triangulations
• The Minimum Number of 4-Cycles in a Maximal Planar Graph with Small Number of Vertices
• Maximising the number of induced cycles in a graph