图的邻点可区别正常边染色

The Adjacent Vertex Distinguishing Proper Edge Coloring of Graphs

图的邻点可区别正常边染色是指图G的一个正常边染色f使得任意相邻两点的着色集合不同.针对染色色数的上界进行研究,通过Vizing定理以及Lovasz一般局部引理,用概率方法得到了邻点可区别正常边染色色数的一个较好的上界Δ+4.

A proper edge coloring of the graph G is called adjacent vertex distinguishing proper edge coloring, for any two adjacent vertices u,v∈E（G）, we have C（u）≠C（v）, where C（u） is called color set of vertex u. In this paper, we studied the upper bound of the adjacent vertex distinguishing proper edge chromatic number and obtained the conclusion that a upper bound on the adjacent vertex distinguishing proper edge chromatic number isΔ ＋ 4 in some conditions by probabilistic method using the Vizing theorem and Lovasz Local Lemma.