1-平面图的结构性质及其在无圈边染色上的应用  

Structural properties of 1-planar graphs and an application to acyclic edge coloring

作　　者：张欣[1] 刘桂真[1] 吴建良[1] 

机构地区：[1]山东大学数学学院,济南250100

出　　处：《中国科学：数学》2010年第10期1025-1032,共8页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:10871119;10971121);高等学校博士学科点专项科研基金(批准号:200804220001)资助项目

摘　　要：一个图称为是1-平面的如果它可以画在一个平面上使得它的每条边最多交叉另外一条边.本文描述了任意1-平面图中小于等于7度点之邻域的局部结构,解决了由Fabrici和Madaras提出的两个关于1-平面图图类中轻图存在性的问题,证明了每个最大度是△的1-平面图G是无圈列表max{2△-2,△+83}-边可选的.A graph is called 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, we establish a local property of 1-planar graphs which describes the structure in the neighborhood of small vertices （i.e., vertices of degree no more than seven）. Meanwhile, some new classes of light subgraphs in 1-planar graphs with the bounded degree are found. Therefore, two open problems presented by Fabrici and Madaras are solved. Furthermore, we prove that each 1-planar graph G with maximum degree △ is acyclically edge L-colorable, where L = max{2△-2, △＋ 83}.

关 键 词：1-平面图 轻图 无圈边染色 列表染色 

分 类 号：O157.5[理学—数学]