Article in press
Authors:
Title:
The planar Turán number of ${\left \{ C_{6}, C_{7} \right \}}$
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-06-15 , Revised: 2025-04-15 , Accepted: 2025-04-16 , Available online: 2025-05-21 , https://doi.org/10.7151/dmgt.2585
Abstract:
Let $\mathcal{H}$ be a set of graphs. A graph is $\mathcal{H}$-free if it does
not contain any copy of $H$ as a subgraph where $H\in \mathcal{H}$. The
planar Turán number of $\mathcal{H}$, denoted by $ex_{p} (n,\mathcal{H})$,
is the maximum number of edges in an $\mathcal{H}$-free planar graph on $n$
vertices. The upper bounds of $ex_{p}(n,\{C_{k},C_{k+1}\})$ are known when
$3\le k\le 5$, and these bounds are tight. In this paper, we give the upper
bound of $ex_{p}(n,\left \{ C_{6},C_{7} \right \})$ for all integers $n\ge 76$,
and this bound is sharp.
Keywords:
Turán number, planar graph, cycle
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).
- D.W. Cranston, B. Lidický, X.N. Liu and A. Shantanam, Planar Turán numbers of cycles: A Counterexample, Electron. J. Combin. 29 (2022) #P3.31.
https://doi.org/10.37236/10774 - C. Dowden, Extremal $C_{4}$-free/$C_{5}$-free planar graphs, J. Graph Theory 83 (2016) 213–230.
https://doi.org/10.1002/jgt.21991 - L.L. Du, B. Wang and M.Q. Zhai, Planar Turán numbers on short cycles of consecutive lengths, Bull. Iranian Math. Soc. 48 (2022) 2395–2405.
https://doi.org/10.1007/s41980-021-00644-1 - L.L. Du and B. Wang, Planar Turán number of $\left \{ C_{5},C_{6} \right \} $, Oper. Res. Trans. (2023) in press.
- D. Ghosh, E. Győri, R.R. Martin, A. Paulos and C.Q. Xiao, Planar Turán number of the $6$-cycle, SIAM J. Discrete Math. 36 (2022) 2028–2050.
https://doi.org/10.1137/21M140657X - E. Győri, A. Li and R. Zhou, The planar Turán number of the seven-cycle (2023).
arXiv: 2307.06909 - E. Győri, K. Varga and X.T. Zhu, A new construction for planar Turán number of cycles, Graphs Combin. 40 (2024) 124.
https://doi.org/10.1007/s00373-024-02822-4 - E. Győri, X.Z. Wang and Z.Y. Zheng, Extremal planar graphs with no cycles of particular lengths (2022).
arXiv: 2208.13477 - P. Keevash, Surveys in Combinatorics (London Math. Soc. Lecture Note Ser., Cambridge University, 2011).
- Y.X. Lan, Y.T. Shi and Z-X. Song, Extremal theta-free planar graphs, Discrete Math. 342 (2019) 111610.
https://doi.org/10.1016/j.disc.2019.111610 - Y.X. Lan and Z-X. Song, An improved lower bound for the planar Turán number of cycles (2022).
arXiv: 2209.01312 - D.R. Lick and A.T. White, $k$-degenerate graphs, Canad. J. Math. 22 (1970) 1082–1096.
https://doi.org/10.4153/CJM-1970-125-1 - D. Offner, Some Turán type results on the hypercube, Discrete Math. 309 (2009) 2905–2912.
https://doi.org/10.1016/j.disc.2008.07.025 - V. Rödl and M. Schacht, Extremal results in random graphs, Bolyai Soc. Math. Stud. 25 (2013) 535–583.
https://doi.org/10.1007/978-3-642-39286-3_20 - R.L. Shi, Z. Walsh and X.X. Yu, Planar Turán number of the $7$-cycle, Eur. J. Combin. 126 (2025) 104134.
https://doi.org/10.1016/j.ejc.2025.104134 - R.L. Shi, Z. Walsh and X.X. Yu, Dense circuit graphs and the planar Turán number of a cycle, J. Graph Theory 108 (2025) 27–38.
https://doi.org/10.1002/jgt.23165 - P. Turán, Eine Extremalautgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941) 436–452.
- W.F. Wang and K.W. Lih, On the sizes of graphs embeddable in surfaces of nonnegative Euler characteristic and their applications to edge choosability, Eur. J. Combin. 28 (2007) 111–120.
https://doi.org/10.1016/j.ejc.2005.09.002 - D.B. West, Introduction to Graph Theory (Prentice Hall, 2001).
Close