图的邻点可区别正常边染色的一些结果

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