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

摘要

如果一个图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.%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.