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

如果一个图G画在平面上有交叉c,则该交叉可以与产生它的两条边所关联的4个顶点所构成的点集合{v_1,v_2,v_3,v_4}建立一个对应关系θ:c→{v_1,v_2,v_3,v_4}。如果对于G中任何两个不同的交叉(如果存在的话)c_1与c_2都有|θ(c_1)?θ(c_2)|≤1,则称图G为NIC-平面图。证明了每个围长至少为5且最小度为4的NIC-平面图含有一条边,其2个顶点的度数都是4,从而每个围长至少为5的NIC-平面图的定向染色数至多为67。