Back to Search Start Over

The maximum number of induced C5's in a planar graph.

Authors :
Ghosh, Debarun
Győri, Ervin
Janzer, Oliver
Paulos, Addisu
Salia, Nika
Zamora, Oscar
Source :
Journal of Graph Theory. Mar2022, Vol. 99 Issue 3, p378-398. 21p.
Publication Year :
2022

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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
03649024
Volume :
99
Issue :
3
Database :
Academic Search Index
Journal :
Journal of Graph Theory
Publication Type :
Academic Journal
Accession number :
154758150
Full Text :
https://doi.org/10.1002/jgt.22745