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

摘要

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c1与c2(如果存在的话),如果｜θ(c1) ∩θ(c2)｜≤1,则称图G是NIC-平面图;如果｜θ(c1)∩θ(c2)｜=0,即θ(c1)∩ θ(c2)=(0),则称图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 θ 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 c1 and c2 (if exist) of a 1-plane graph G,if |θ(c1) ∩ θ(c2)| ≤ 1,then G is an NIC-planar graph,and if ｜θ(c1) ∩ θ(c2)｜ =0,that is,θ(c1) ∩ θ(c2) =（0）,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-1-planar graph,and such an embedding of G is an outer-1-plane graph.This paper surveys the results on the colorings of the above four classes of graphs.