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

Expand
  • 1. School of Mathematical and Statistics, Xidian University, Xi'an 710071, China

Received date: 2017-07-07

  Online published: 2017-12-15

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.

Cite this article

ZHANG Xin, LIU Weichan . The coloring of the class of 1-planar graphs and its subclasses[J]. Operations Research Transactions, 2017 , 21(4) : 135 -152 . DOI: 10.15960/j.cnki.issn.1007-6093.2017.04.009

Outlines

/