论文部分内容阅读
设图G(V,E)为简单图，给定图G的一个边染色(Φ)，顶点x∈V(G)的颜色集是指与顶点x相关联的边所染的颜色构成的集合，记作S(Φφ)(x)。
如果对于图G的任意两个相邻顶点x，y，有S(Φ)(x)≠S(y)，此边染色(Φ)称为图G的邻点可区分边染色，简称nd边染色。根据外平面图的一些结构特征，将二连通外平面图邻点可区分边色数的上界改进为4，并由某些特殊的二连通外平面图的邻点可区分边色数的分析，如：不含三角形面的二连通外平面图、对偶图为树的二连通外平面图等，最终将二连通外平面图邻点可区分边色数上界改进为3。