An improved lower bound for the planar Tur\'an number of cycles

arXiv2209.01312MaRDI QIDQ6409622FDOQ6409622

Publication date: 2 September 2022

Abstract: The planar Tur'an number of a graph

H

, denoted by

e x_{_{m} a t h c a l P} (n, H)

, is the largest number of edges in a planar graph on

n

vertices without containing

H

as a subgraph. In this paper, we continue to study the topic of "extremal" planar graphs initiated by Dowden [J. Graph Theory 83 (2016) 213--230]. We first obtain an improved lower bound for

e x_{_{m} a t h c a l P} (n, C_{k})

for all

k g e 13

and

n g e 5 (k - 6 + l f l o o r (k - 1) / 2 f l o o r) (k - 1) / 2

; the construction for each

k

and

n

provides a simpler counterexample to a conjecture of Ghosh, GyH{o}ri, Martin, Paulos and Xiao [arxiv:2004.14094v1], which has recently been disproved by Cranston, Lidick'y, Liu and Shantanam [Electron. J. Combin. 29(3) (2022) #P3.31] for every

k g e 11

and

n

sufficiently large (as a function of

k

). We then prove that

e x_{_{m} a t h c a l P} (n, H^{+}) = e x_{_{m} a t h c a l P} (n, H)

for all

k g e 5

and

n g e | H | + 1

, where

H i n C_{k}, 2 C_{k}

and

H^{+}

is obtained from

H

by adding a pendant edge to a vertex of degree two.

This page was built for publication: An improved lower bound for the planar Tur\'an number of cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6409622)