| NIC-平面图中的轻边存在性及其定向染色 |
| |
| 引用本文： | 刘维婵.NIC-平面图中的轻边存在性及其定向染色[J].计算机工程与应用,2018,54(7):62-65. |
| |
| 作者姓名： | 刘维婵 |
| |
| 作者单位： | 西安电子科技大学 数学与统计学院，西安 710071 |
| |
| 摘 要： | 如果一个图G]画在平面上有交叉c]，则该交叉可以与产生它的两条边所关联的4个顶点所构成的点集合{v1,v2,v3,v4}]建立一个对应关系θ:c→{v1,v2,v3,v4}]。如果对于G]中任何两个不同的交叉（如果存在的话）c1]与c2]都有|θ(c1)?θ(c2)|≤1]，则称图G]为NIC-平面图。证明了每个围长至少为5且最小度为4的NIC-平面图含有一条边，其2个顶点的度数都是4，从而每个围长至少为5的NIC-平面图的定向染色数至多为67。
|
| 关 键 词： | NIC-平面图 轻边 权转移方法 定向染色 |
Existence of light edge and oriented coloring of NIC-planar graphs |
| |
| LIU Weichan.Existence of light edge and oriented coloring of NIC-planar graphs[J].Computer Engineering and Applications,2018,54(7):62-65. |
| |
| Authors: | LIU Weichan |
| |
| Affiliation: | School of Mathematics and Statistics, Xidian University, Xi’an 710071, China |
| |
| Abstract: | If there exists a crossing c in a graph G drawn on the plane, this crossing induces a function θ:c→]{v1,v2,]v3,v4}], where {v1,v2,v3,v4}] is a set of four vertices that are the ones incident with the two crossed edges generating the crossing c. If |θ(c1)∩θ(c2)|≤1] for any two distinct crossings c1 and c2（if exist） in G, G is a NIC-planar graph. It is proven that every NIC-planar graph with girth at least 5 and minimum degree 4 contains an edge with the degrees of the two adjacent vertices both being 4. As a consequence, it deduces that the oriented chromatic number of any NIC-planar graph with girth at least 5 is at most 67. |
| |
| Keywords: | NIC-planar graph light edge discharging method oriented coloring |
|
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
