计算机工程与应用2018，Vol.54Issue(7)：62-65,4.DOI:10.3778/j.issn.1002-8331.1612-0160
NIC-平面图中的轻边存在性及其定向染色
Existence of light edge and oriented coloring of NIC-planar graphs
摘要
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 c1and 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 adja-cent 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.关键词
NIC-平面图/轻边/权转移方法/定向染色Key words
NIC-planar graph/light edge/discharging method/oriented coloring分类
数理科学引用本文复制引用
刘维婵..NIC-平面图中的轻边存在性及其定向染色[J].计算机工程与应用,2018,54(7):62-65,4.基金项目
国家级大学生创新创业训练计划(2017年度). （2017年度）
