计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (7): 62-65.DOI: 10.3778/j.issn.1002-8331.1612-0160

• 理论与研发 • 上一篇    下一篇

NIC-平面图中的轻边存在性及其定向染色

刘维婵   

  1. 西安电子科技大学 数学与统计学院,西安 710071
  • 出版日期:2018-04-01 发布日期:2018-04-16

Existence of light edge and oriented coloring of NIC-planar graphs

LIU Weichan   

  1. School of Mathematics and Statistics, Xidian University, Xi’an 710071, China
  • Online:2018-04-01 Published:2018-04-16

摘要: 如果一个图[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-平面图, 轻边, 权转移方法, 定向染色

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.

Key words: NIC-planar graph, light edge, discharging method, oriented coloring