English

运筹学学报

• 运筹学 • 上一篇    

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

张欣1,*  刘维婵1   

  1. 1. 西安电子科技大学数学与统计学院，西安 710071
  • 收稿日期:2017-07-07 出版日期:2017-12-15 发布日期:2017-12-15
  • 通讯作者: 张欣 xzhang@xidian.edu.cn
  • 基金资助:

    陕西省自然科学基础研究计划面上基金(No. 2017JM1010),  中央高校基本科研业务费(No. JB170706),  国家自然科学基金青年科学基金(No. 11301410), 国家级大学生创新创业训练计划(No. 201710701125)

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

ZHANG Xin1,*   LIU Weichan1   

  1. 1. School of Mathematical and Statistics, Xidian University, Xi'an 710071, China
  • Received:2017-07-07 Online:2017-12-15 Published:2017-12-15

PDF

481

摘要：

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

关键词: 1-平面图, NIC-平面图, IC-平面图, 外1-平面图, 染色

Abstract:

 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 \theta 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 c_1 and c_2 (if exist) of a 1-plane graph G, if |\theta(c_1)\cap \theta(c_2)|\leq 1, then G is an NIC-planar graph, and if |\theta(c_1)\cap \theta(c_2)|=0, that is, \theta(c_1)\cap \theta(c_2)=\varnothing, 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.

Key words: 1-planar graph, NIC-planar graph, IC-planar graph, outer-1-planar graph, coloring