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

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

Abstract

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

CLC Number:

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.

References

[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.

Planar Turán number and planar anti-Ramsey number of graphs

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Yanxia DONG, Tao XUE, Guang ZHANG. k-tuple domination in generalized de Bruijn digraphs [J]. Operations Research Transactions, 2021, 25(2): 127-134.
[2]	Yao LIU. On (1, 0)-relaxed strong edge-coloring of graphs [J]. Operations Research Transactions, 2021, 25(2): 115-126.
[3]	Xiaoxia LIN. A note on quasi k-connected graphs [J]. Operations Research Transactions, 2021, 25(1): 137-140.
[4]	Min CHEN, Jianmin YANG, Hao ZHANG, Yiting WANG. Weakly entire coloring of outerplanar graphs [J]. Operations Research Transactions, 2021, 25(1): 132-136.
[5]	Jing ZHAO, Erfang SHAN, Jiagui ZHAO. Sufficient conditions for hypergraphs to be maximally edge-connected and super-edge-connected [J]. Operations Research Transactions, 2021, 25(1): 123-131.
[6]	TAO Yanliang, HUANG Qiongxiang, CHEN Lin. Contraction graph method for the interval edge-colorings of graphs [J]. Operations Research Transactions, 2019, 23(2): 31-43.
[7]	LIU Yan, LEI Mengxia, HUANG Xiaoxian. Path-transformation graph of maximum matchings [J]. Operations Research Transactions, 2019, 23(2): 104-112.
[8]	LUO Zhaoyang, SUN Lin. The linear aboricity of planar graphs with 6-cycles containing at most one chord [J]. Operations Research Transactions, 2019, 23(2): 113-119.
[9]	PEI Jianfeng, LIN Shangwei. Two sufficient conditions for maximally restricted-edge-connected hypergraphs [J]. Operations Research Transactions, 2019, 23(2): 120-126.
[10]	SUN Qiushi, YANG Xiaoyun, WANG Ligong, LI Xihe, WANG Pengchao. Laplacian spectral characterizations of new unicyclic graphs H(p,tK_1,m) [J]. Operations Research Transactions, 2019, 23(1): 72-80.
[11]	CHEN Yuanyuan, WANG Guoping. On the signless Laplacian spectral radius of tricyclic graphs [J]. Operations Research Transactions, 2019, 23(1): 81-89.
[12]	CHEN Hongyu, TAN Xiang. An upper bound of the linear 2-arboricity of planar graphs with neither 5-cycles nor adjacent 4-cycles [J]. Operations Research Transactions, 2019, 23(1): 104-110.
[13]	REN Jiamin, FENG Wei, ZHAO Lingqi, WANG Shiying, JIRIMUTU. The 1-good-neighbor diagnosability of the Cayley graphs UG_n generated by unicyclic graphs under the PMC model and the MM^* model [J]. Operations Research Transactions, 2019, 23(1): 97-103.
[14]	MEI Ruoxing, WANG Ligong, WANG Luhua, WANG Zhanqing. Laplacian spectral characterizations of unicyclic graphs H( p, t K_{ 1, m}) [J]. Operations Research Transactions, 2015, 19(1): 57-64.
[15]	HU Xiaochen, HE Weili, HAO Rongxia. Balanced judicious partitions of graphs with $\Delta($G$)-\delta($G$)\leq$2 [J]. Operations Research Transactions, 2015, 19(1): 108-116.