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

作者：赵新梅; 曾贤灏

来源：兰州工业高等专科学校学报, 2016, 23(02): 90-92.

• Vizing定理
• 邻点可区别正常边色数
• Lovasz局部引理

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

• 出版日期2016
• 单位兰州工业学院