The Planar Turán Number of {K4,C5} and {K4,C6}

Győri, Ervin and Li, Alan and Zhou, Runtian (2024) The Planar Turán Number of {K4,C5} and {K4,C6}. GRAPHS AND COMBINATORICS, 40 (5). ISSN 0911-0119

Preview

Text s00373-024-02830-4.pdf - Published Version Download (548kB) | Preview

Abstract

Let H be a set of graphs. The planar Turán number, exP(n,H), is the maximum number of edges in an n-vertex planar graph which does not contain any member of H as a subgraph. When H={H} has only one element, we usually write exP(n,H) instead. The study of extremal planar graphs was initiated by Dowden (J Graph Theory 83(3):213–230, 2016). He obtained sharp upper bounds for both exP(n,C5) and exP(n,K4). Later on, sharp upper bounds were proved for exP(n,C6) and exP(n,C7). In this paper, we show that exP(n,{K4,C5})≤157(n-2) and exP(n,{K4,C6})≤73(n-2). We also give constructions which show the bounds are sharp for infinitely many n. © The Author(s) 2024.

Actions (login required)

Edit Item