论文部分内容阅读
一个图G的正常边染色称为是邻点可区别的，如果对G的任意两个相邻的顶点u和v来说，与u关联的所有边的颜色构成的集合异于与v关联的所有边的颜色构成的集合.显然一个图G有邻点可区别正常边染色当且仅当G不含孤立边.对一个无孤立边的图G进行邻点可区别的正常边染色所需要的最少的颜色数称为是G的邻点可区别正常边色数，记为χa(G).本文对Pm×Pn，Pm×Gn，Pkn，单圈图及几类完全4-部图的邻点可区别正常边染色进行了讨论，确定了它们的邻点可区别正常边色数.这些结果说明，邻点可区别正常边染色猜想(对任意连通简单图G，如果|V(G)|≥6，则△(G)≤χa(G)≤△(G)+2)对这些图是成立的.对最小度至少是5，最大度小于2(cn+1)/7的n阶图G，给出了其邻点可区别的正常边色数的一个上界[cn]，其中实数c满足0＜c≤7/8。