Structural properties of 1-planar graphs and an application to acyclic edge coloring
Liu Gui · Scientia Sinica Mathematica · 2010
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}.