Extremal C4-free/C5-free planar graphs

2015/12/14 by Chris Dowden, Dowden, Chris · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1512.04385

openalex publication_date 2015/12/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the topic of "extremal" planar graphs, defining \mathrmex__P(n,H) to be the maximum number of edges possible in a planar graph on n vertices that does not contain a given graph H as a subgraph. In particular,we examine the case when H is a small cycle,obtaining \mathrmex__P(n,C₄) ≤ (15)/(7)(n-2) for all n ≥ 4 and \mathrmex__P(n,C₅) ≤ (12n-33)/(5) for all n ≥ 11, and showing that both of these bounds are tight.

Cited by

• Rainbow planar Turán numbers of cycles
• Planar Turán numbers of three configurations
• Planar Turán number of disjoint union of C₃ and C₅
• Planar Turán number of quasi-double stars

Related

• Extremal H-free planar graphs
• Extremal Theta-free planar graphs
• Extremal planar graphs with no cycles of particular lengths
• Extremal problems on planar graphs without k edge-disjoint cycles
• The planar Turán number of \K₄,C₅\ and \K₄,C₆\