图的平面Turán数和平面anti-Ramsey数

doi:10.15960/j.cnki.issn.1007-6093.2021.03.013

摘要/Abstract

摘要： 在所有顶点数为$n$且不包含图$G$作为子图的平面图中，具有最多边数的图的边数称为图$G$的平面Turán数，记为$ex_{_\mathcal{P}}（n，G）$。给定正整数$n$以及平面图$H$，用$\mathcal{T}_n （H）$来表示所有顶点数为$n$且不包含$H$作为子图的平面三角剖分图所组成的图集合。设图集合$\mathcal{T}_n （H）$中的任意平面三角剖分图的任意$k$边染色都不包含彩虹子图$H$，则称满足上述条件的$k$的最大值为图$H$的平面anti-Ramsey数，记作$ar_{_\mathcal{P}}（n，H）$。两类问题的研究均始于2015年左右，至今已经引起了广泛关注。全面地综述两类问题的主要研究成果，以及一些公开问题。

关键词: 平面Turán数, 平面anti-Ramsey数, Theta图

Abstract: The planar Turán number of a graph $G$, denoted $ex_{_\mathcal{P}}(n,G)$, is the maximum number of edges in a planar graph on $n$ vertices without containing $G$ as a subgraph. Given a positive integer $n$ and a plane graph $H$, let $\mathcal{T}_n(H)$ be the family of all plane triangulations $T$ on $n$ vertices such that $T$ contains $H$ as a subgraph. The planar anti-Ramsey number of $H$, denoted $ar_{_\mathcal{P}}(n, H)$, is the maximum number $k$ such that no edge-coloring of any plane triangulation in $\mathcal{T}_n(H)$ with $k$ colors contains a rainbow copy of $H$. The study of these two topics was initiated around 2015, and has attracted extensive attention. This paper surveys results about planar Turán number and planar anti-Ramsey number of graphs. The goal is to give a unified and comprehensive presentation of the major results, as well as to highlight some open problems.

Key words: planar Turán number, planar anti-Ramsey number, Theta graph

中图分类号:

兰永新, 史永堂, 宋梓霞. 图的平面Turán数和平面anti-Ramsey数[J]. 运筹学学报, 2021, 25(3): 200-216.

LAN Yongxin, SHI Yongtang, SONG Zixia. Planar Turán number and planar anti-Ramsey number of graphs[J]. Operations Research Transactions, 2021, 25(3): 200-216.

参考文献

[1] Turán P. Eine Extremalaufgabe aus der Graphentheorie[J]. Matematikai és Fizikai Lapok, 1941, 48:436-452.
[2] Erdős P, Stone A H. On the structure of linear graphs[J]. Bulletin of the American Mathematical Society, 1946, 52:1087-1091.
[3] Bollobás B. Modern Graph Theory[M]. New York:Springer, 2013.
[4] Füredi Z, Jiang T. Hypergraph Turán numbers of linear cycles[J]. Journal of Combinatorial Theory, Series A, 2014, 123:252-270.
[5] Füredi Z, Jiang T, Seiver R. Exact solution of the hypergraph Turán problem for k-uniform linear paths[J]. Combinatorica, 2014, 34:299-322.
[6] Kostochka A, Mubayi D, Verstraëte J. Turán problems and shadows I:Paths and cycles[J]. Journal of Combinatorial Theory, Series A, 2015, 129:57-79.
[7] Füredi Z. Turán type problems, "Surveys in Combinatorics"[J]. London Mathematical Society, 1991, 166:253-300.
[8] Keevash P. Hypergraph Turán problems, "Surveys in Combinatorics 2011"[J]. London Mathematical Society, 2011, 392:83-139.
[9] Dowden C. Extremal C4-free/C5-free planar graphs[J]. Journal of Graph Theory, 2016, 83:213-230.
[10] Erdős P, Simonovits M, Sós V T. Anti-Ramsey theorems[J]. Colloquia Mathematica Societatis János Bolyai, 1975, 10:633-643.
[11] Horňák M, Jendrol0 S, Schiermeyer I, et al. Rainbow numbers for cycles in plane triangulations[J]. Journal of Graph Theory, 2015, 78:248-257.
[12] Lan Y, Shi Y, Song Z X. Planar anti-Ramsey numbers of paths and cycles[J]. Discrete Mathematics, 2019, 342:3216-3224.
[13] Lan Y, Shi Y, Song Z X. Extremal H-free planar graphs[J]. The Electronic Journal of Combinatorics, 2019, 26(2):#P2.11.
[14] Dzido T. A note on Turán numbers for even wheels[J]. Graphs and Combinatorics, 2013, 29:1305-1309.
[15] Dzido T, Jastrzȩbski A. Turán numbers for odd wheels[J]. Discrete Mathematics, 2018, 341:1150-1154.
[16] Fang L, Zhai M, Wang B. Planar Turán number of intersecting triangles[J]. arXiv:2007.09650v1.
[17] Wang W, Lih K. On the sizes of graphs embeddable in surfaces of nonnegative Euler characteristic and their applications to edge choosability[J]. European Journal of Combinatorics, 2007, 28:111-120.
[18] Lan Y, Shi Y, Song Z X. Extremal Theta-free planar graphs[J]. Discrete Mathematics, 2019, 342:111610.
[19] Ghosh D, Győri E, Martin R, et al. Planar Turán number of the 6-cycle[J]. arXiv:2004.14094v1.
[20] Ghosh D, Győri E, Paulos A, et al. Planar Turán number of the Θ_6[J]. arXiv:2006.00994v1.
[21] Faudree R, Schelp R. Path Ramsey numbers in multicolourings[J]. Journal of Combinatorial Theory, Series B, 1975, 19:150-160.
[22] Lan Y, Shi Y, Song Z X. Planar Turán numbers for Theta graphs and paths of small order[J]. arXiv:1711.01614v1.
[23] Lan Y, Shi Y. Planar Turán numbers of short paths[J]. Graphs and Combinatorics, 2019, 35:1035-1049.
[24] Qin Z, Lan Y, Shi Y, et al. Exact rainbow numbers for matchings in plane triangulations[J]. Discrete Mathematics, 2021, 344(4):112301.
[25] Jin Z, Ye K. Rainbow number of matchings in planar graphs[J]. Discrete Mathematics, 2018, 341:2846-2858.
[26] Sang L, Wang H, Ye K. Rainbow number of matchings in Halin graphs[J]. Journal of Mathematics and Computer Science, 2019, 9:33-45.
[27] Qin Z, Lei H, Li S. Rainbow numbers for small graphs in planar graphs[J]. Applied Mathematics and Computation, 2020, 371:124888.
[28] Qin Z, Li S, Lan Y, et al. Rainbow numbers for paths in planar graphs[J]. Applied Mathematics and Computation, 2021, 397:125918.
[29] Jendrol' S, Schiermeyer I, Tu J. Rainbow numbers for matchings in plane triangulations[J]. Discrete Mathematics, 2014, 331:158-164.
[30] Qin Z, Lan Y, Shi Y. Improved bounds for rainbow numbers of matchings in plane triangulations[J]. Discrete Mathematics, 2019, 342:221-225.
[31] Chen G, Lan Y, Song Z X. Planar anti-Ramsey numbers of matchings[J]. Discrete Mathematics, 2019, 342:2106-2111.
[32] Győri E, Paulos A, Salia N, et al. Generalized planar Turán numbers[J]. arXiv:2002.04579v2.
[33] Alon N, Caro Y. On the number of subgraphs of prescribed type of planar graphs with a given number of vertices[J]. Annals Discrete Mathematics, 1984, 20:25-36.
[34] Cox C, Martin R. Counting paths, cycles and blow-ups in planar graphs[J]. arXiv:2101.05911v1.
[35] Eppstein D. Connectivity, graph minors and subgraph multiplicity[J]. Journal of Graph Theory, 1993, 17(3):409-416.
[36] Hakimi S, Schmeichel E. On the number of cycles of length k in a maximal planar graph[J]. Journal of Graph Theory, 1979, 3(1):69-86.
[37] Huynh T, Joret G, Wood D. Subgraph densities in a surface[J]. arXiv:2003.13777v1.
[38] Matolcsi D, Nagy Z. Generalized outerplanar Turán numbers and maximum number of k-vertex subtrees[J]. arXiv:2102.11746v1.
[39] Wood D. On the maximum number of cliques in a graph[J]. Graphs and Combinatorics, 2007, 23:337-352.
[40] Wormald N. On the frequency of 3-connected subgraphs of planar graphs[J]. Bulletin of the Australian Mathematical Society, 1986, 34(2):309-317.
[41] Győri E, Paulos A, Salia N, et al. The maximum number of pentagons in a planar graph[J]. arXiv:1909.13532v1.
[42] Ghosh D, Győri E, Janzer O, et al. The maximum number of induced C₅'s in a planar graph[J]. arXiv:2004.01162v1.
[43] Győri E, Paulos A, Salia N, et al. The maximum number of paths of length three in a planar graph[J]. arXiv:1909.13539v1.
[44] Ghosh D, Győri E, Martin R, et al. The maximum number of paths of length four in a planar graph[J]. Discrete Mathematics, 2021, 344:112317.