论文部分内容阅读
具有重要的理论意义和实用价值的各种染色问题,一直是图论中的热点话题之一。离散系统、组合分析中的许多问题都可转化为图着色问题,例如,不含给定图G作为子图的n个顶点的图的边的最大数目就依赖于G的色数。因此TR.Jensen和B.Toft断言:图着色理论在离散数学中处于中心的地位。在现实生活中许多领域都会涉及到将某种对象的集合按照一定的规则进行分类的问题,例如时间表问题、排序问题、排课表问题、存储问题、电路安排、任务分配等等,都与图着色理论密切相关,也正是图着色理论的实际应用才引起了世人的兴趣。
所谓图着色是指对图中的顶点、边(对平面图而言还有面)等元素按照一定的规则进行分类。对象不同或规则不同,便有各式各样的着色,继图的点着色、边着色以及组合地图的面着色之后,人们又提出了全色数的概念。如点着色、边着色、全着色、强染色、邻强边着色、邻点可区别全染色、点可区别边染色、边面着色、完美着色等成百上千种着色方式。
为了恰当地表示大型超网络、存储问题、时间安排和任务分配等研究课题中各元素之间的关系,图的染色理论做为一种可行的工具被自然的引入。由于其良好的应用背景,图的染色理论已成为现在图论领域中迅速发展的子学科之一。
本论文首先综述了全染色的基本概念和研究现状,然后统一各种文献中有关染色的概念。文章根据全着色理论得出了若干图的全色数,并通过对这些图的全色数的确定验证全着色猜想(TCC),得出了全着色方面的一些定理,在全着色的实际应用中,给出了某些图的全着色算法。
其次,文章引入邻点可区别全着色,邻点可区别全着色是全着色理论的一个最新研究方向,张忠辅等人提出图的邻点可区别全着色这个概念,得到了若干结果,并提出了有关猜想,目前所知结果甚少,尚有许多未解决的问题,邻点可区别全着色理论是本文的研究重点,给出了几类图的邻点可区别全色数,验证了邻点可区别全着色猜想。