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

The Adjacent Vertex Distinguishing Proper Edge Coloring of Graphs

作　　者：赵新梅[1] 曾贤灏[2] 

机构地区：[1]兰州工业学院基础学科部,甘肃兰州730050 [2]兰州工业学院学报编辑部,甘肃兰州730050

出　　处：《兰州工业学院学报》2016年第2期90-92,共3页Journal of Lanzhou Institute of Technology

摘　　要：图的邻点可区别正常边染色是指图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.

关 键 词：Vizing定理 邻点可区别正常边色数 Lovasz局部引理 

分 类 号：O157.5[理学—数学]