1-平面图及其子类的染色

The coloring of the class of 1-planar graphs and its subclasses

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果.

A graph G is 1-planar if it can be embedded on a plane so that each edge is crossed by at most one other edge, and such a 1-planar embedding of G is a 1-plane graph. Since every crossing c in a 1-plane graph is generalized by one edge crossing the other edge, there is a mapping 0 from c to a set of four vertices of G that are the end-vertices of the two edges crossing at c. For any two distinct crossings cl and c2 （if exist） of a 1-plane graph G, if ｜θ（c1）∩θ（c2）｜≤1, then G is an NIC-planar graph, and if [｜θ（c_1）∩θ（c_2）｜=0,that is ,θ（c_1）∩θ（c_2）=？, then G is an IC-planar graph. If a graph G can be embedded on a plane so that all vertices are on its outerface and each edge is crossed by at most one other edge, then G is an outer-l-planar graph, and such an embedding of G is an outer-l-plane graph. This paper surveys the results on the colorings of the above four classes of graphs.