论文部分内容阅读
如果一个图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。