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

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

一个图称为是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}.