图的平面Turán数和平面anti-Ramsey数（英文）

作者：兰永新; 史永堂^*; 宋梓霞

来源：运筹学学报, 2021, 25(03): 200-216.

DOI：10.15960/j.cnki.issn.1007-6093.2021.03.013

• 平面Turán数
• 平面anti-Ramsey数
• Theta图

在所有顶点数为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年左右,至今已经引起了广泛关注。全面地综述两类问题的主要研究成果,以及一些公开问题。

• 单位
  南开大学; 河北工业大学