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

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

作　　者：兰永新 史永堂[2] 宋梓霞 LAN Yongxin;SHI Yongtang;SONG Zixia(School of Science,Hebei University of Technology,Tianjin 300401,China;Center for Combinatorics and LPMC,Nankai University,Tianjin 300071,China;Department of Mathematics,University of Central Florida,Orlando,FL 32816,USA)

机构地区：[1]河北工业大学理学院,天津300401 [2]南开大学组合数学中心,天津300071 [3]中佛罗里达大学数学系,奥兰多FL32816,美国

出　　处：《运筹学学报》2021年第3期200-216,共17页Operations Research Transactions

基　　金：国家自然科学基金(Nos.12001154,11922112,11771221);美国国家科学基金(No.DMS-1854903);天津市自然科学基金(Nos.20JCJQJC00090,20JCZDJC00840);中央高校南开大学基本科研业务费专项资金(No.63213037);天津市共建高校专项资金(No.280000307)。

摘　　要：在所有顶点数为n且不包含图G作为子图的平面图中,具有最多边数的图的边数称为图G的平面Turán数,记为exP(n,G)。给定正整数n以及平面图H,用Tn(H)来表示所有顶点数为n且不包含H作为子图的平面三角剖分图所组成的图集合。设图集合Tn(H)中的任意平面三角剖分图的任意k边染色都不包含彩虹子图H,则称满足上述条件的k的最大值为图H的平面anti-Ramsey数,记作arP(n,H)。两类问题的研究均始于2015年左右,至今已经引起了广泛关注。全面地综述两类问题的主要研究成果,以及一些公开问题。The planar Turán number of a graph G,denoted exP(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 Tn(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 arP(n,H),is the maximum number k such that no edge-coloring of any plane triangulation in Tn(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.

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

分 类 号：O157.5[理学—数学] O157.6[理学—基础数学]