Operations Research Transactions >
2017 , Vol. 21 >Issue 4: 135 - 152
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2017.04.009
The coloring of the class of 1-planar graphs and its subclasses
Received date: 2017-07-07
Online published: 2017-12-15
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, 2017 , 21(4) : 135 -152 . DOI: 10.15960/j.cnki.issn.1007-6093.2017.04.009
/
| 〈 |
|
〉 |