APP下载

完全图的点可区别V-全染色

2011-06-09马宝林河南科技学院河南新乡453003

马宝林(河南科技学院,河南新乡453003)

完全图的点可区别V-全染色

马宝林
(河南科技学院,河南新乡453003)

根据图的点可区别全染色的概念及其染色方法,讨论了图的点可区别V-全染色,给出了完全图Kn的点可区别V-全色数的结论及其证明,为进一步探讨其他简单图的点可区别V-全染色提供了理论证据,丰富了图的点可区别V-全染色的结果.

简单图;点可区别V-全染色;点可区别V-全色数;完全图

图论是一个应用十分广泛而又极其有趣的数学分支,它的研究开始于200多年前,它的第一篇论文是1736年Euler发表的,其主要内容是利用图论的方法解决了当时著名的格尼斯堡七桥问题.20世纪60年代以来,图论在科学界异军突起,活跃非凡,在解决物理学、化学、生物学、信息与计算机科学以及社会科学等诸多学科问题中,图论已显示出极大的优越性.但当前对图论研究比较活跃的两类问题是图的匹配问题和图的染色问题.而全染色又是染色的一个传统问题,目前已经得到很多重要的结果.2004年,在全染色的基础上,张忠辅、陈祥恩等提出了图的邻点可区别全染色这一新概念[1],在图论的染色理论中产生了新的有趣课题,并且现已得到了一些有价值的成果.2008年,在点可区别正常全染色的基础上,张忠辅、陈祥恩等又提出了图的点可区别一般全染色[2].本文将根据图的点可区别全染色的概念及其染色方法,讨论图的点可区别V-全染色,给出完全图Kn的点可区别V-全色数的……

登录APP查看全文