Operations Research Transactions
Previous Articles
ZHANG Xin1,* LIU Weichan1
Received:
Online:
Published:
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
ZHANG Xin, LIU Weichan. The coloring of the class of 1-planar graphs and its subclasses[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2017.04.009.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2017.04.009
https://www.ort.shu.edu.cn/EN/Y2017/V21/I4/135