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

Debarun Ghosh; Ervin Győri; Oliver Janzer; Addisu Paulos; Nika Salia; Oscar Zamora

doi:10.1002/jgt.22745

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

Debarun Ghosh
, Ervin Győri
, Oliver Janzer^*
, Addisu Paulos
, Nika Salia
, Oscar Zamora

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

Finding the maximum number of induced cycles of length (Formula presented.) in a graph on (Formula presented.) 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 (Formula presented.). In this paper we determine precisely, for all sufficiently large (Formula presented.), the maximum number of induced 5-cycles that an (Formula presented.) -vertex planar graph can contain.

Original language	English
Pages (from-to)	378-398
Number of pages	21
Journal	Journal of Graph Theory
Volume	99
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22745
State	Published - Mar 2022
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2021 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/jgt.22745

Cite this

@article{a5f2a24bb9544cee81ba5b6e2fbad458,

title = "The maximum number of induced C5's in a planar graph",

abstract = "Finding the maximum number of induced cycles of length (Formula presented.) in a graph on (Formula presented.) vertices has been one of the most intriguing open problems of Extremal Graph Theory. Recently Balogh, Hu, Lidick{\'y} and Pfender answered the question in the case (Formula presented.). In this paper we determine precisely, for all sufficiently large (Formula presented.), the maximum number of induced 5-cycles that an (Formula presented.) -vertex planar graph can contain.",

author = "Debarun Ghosh and Ervin Gy{\H o}ri and Oliver Janzer and Addisu Paulos and Nika Salia and Oscar Zamora",

note = "Publisher Copyright: {\textcopyright} 2021 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC",

year = "2022",

month = mar,

doi = "10.1002/jgt.22745",

language = "English",

volume = "99",

pages = "378--398",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

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

AU - Ghosh, Debarun

AU - Győri, Ervin

AU - Janzer, Oliver

AU - Paulos, Addisu

AU - Salia, Nika

AU - Zamora, Oscar

PY - 2022/3

Y1 - 2022/3

N2 - Finding the maximum number of induced cycles of length (Formula presented.) in a graph on (Formula presented.) 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 (Formula presented.). In this paper we determine precisely, for all sufficiently large (Formula presented.), the maximum number of induced 5-cycles that an (Formula presented.) -vertex planar graph can contain.

AB - Finding the maximum number of induced cycles of length (Formula presented.) in a graph on (Formula presented.) 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 (Formula presented.). In this paper we determine precisely, for all sufficiently large (Formula presented.), the maximum number of induced 5-cycles that an (Formula presented.) -vertex planar graph can contain.

UR - https://www.scopus.com/pages/publications/85115626070

U2 - 10.1002/jgt.22745

DO - 10.1002/jgt.22745

M3 - Article

AN - SCOPUS:85115626070

SN - 0364-9024

VL - 99

SP - 378

EP - 398

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -