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

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

在所有顶点数为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.