Planar Turán number of the 6-cycle

DOI10.1137/21M140657XMaRDI QIDQ5099104zbMATH OpenOpenAlexFDO

Authors Debarun Ghosh, Ryan R. Martin, Addisu Paulos, Chuanqi Xiao, Ervin Győri

Publication date 31 August 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.14094

zbMATH Keywords

extremal planar graphplanar Turán number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: Let ${mex}_{mathcalP}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, ${mex}_{mathcalP}(n,T,H)$ is the well studied function, the planar Tur'an number of $H$, denoted by ${mex}_{mathcalP}(n,H)$. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both ${mex}_{mathcalP}(n,C_4)$ and ${mex}_{mathcalP}(n,C_5)$. Later on, Y. Lan, et al. continued this topic and proved that ${mex}_{mathcalP}(n,C_6)leqfrac18(n-2)7$. In this paper, we give a sharp upper bound ${mex}_{mathcalP}(n,C_6)leqfrac52n-7$, for all $ngeq18$, which improves Lan's result. We also pose a conjecture on ${mex}_{mathcalP}(n,C_k)$, for $kgeq7$.

Recommendations

• Planar Turán numbers on short cycles of consecutive lengths
• Planar Turán numbers of cycles: a counterexample
• Planar Turán numbers of short paths
• Generalized planar Turán numbers
• Extremal \(C_{4}\)-free/\(C_{5}\)-free planar graphs

Cites work

• Extremal \(C_{4}\)-free/\(C_{5}\)-free planar graphs
• Extremal \(H\)-free planar graphs
• Extremal Theta-free planar graphs
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• On the structure of linear graphs
• Planar Turán number of intersecting triangles
• The Turán number of the triangular pyramid of 3-layers

Cited in

(30)

• Planar Turán numbers on short cycles of consecutive lengths
• Planar Turán number of intersecting triangles
• Extremal Theta-free planar graphs
• Planar Turán numbers of short paths
• Extremal \(H\)-free planar graphs
• Generalized planar Turán numbers
• Extremal \(C_{4}\)-free/\(C_{5}\)-free planar graphs
• Outerplanar Turán numbers of cycles and paths
• Planar Turán numbers of cubic graphs and disjoint union of cycles
• Planar Turán number of the disjoint union of cycles
• Planar graphs with the maximum number of induced 6-cycles
• An improved upper bound for planar Turán number of double star \(S_{2 , 5}\)
• The planar Turán number of \(\{K_4, C_5\}\) and \(\{K_4, C_6\}\)
• Dense circuit graphs and the planar Turán number of a cycle
• A new construction for the planar Turán number of cycles
• The planar Turán number of _6-graphs
• The planar Turán number of \({\left \{ C_6, C_7 \right \}}\)
• The extremal spectral radius of outerplanar graphs without C_k
• The maximum spectral radius of planar graphs without the join of K₂ and a linear forest
• On the spectral extremal problem of planar graphs
• The planar Turán number of double star \(S_{2,4}\)
• The planar Turán number of double stars \(S_{2,l}\)
• Planar Turán number of the 7-cycle
• Planar Turán number of two adjacent cycles
• Generalized planar Turán numbers related to short cycles
• Planar Turán number of quasi-double stars
• Density and degeneracy of NIC-planar graphs
• Planar Turán numbers of three configurations
• The planar Turán number of double star \(S_{3,5}\)
• Faces in girth-saturated graphs on surfaces

This page was built for publication: Planar Turán number of the 6-cycle

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