论文部分内容阅读
具有重要理论意义和实用价值的染色问题,一直是图论中的热点话题之一.离散系统、组合分析中的许多问题都可转化为图着色问题,例如,不含给定图G作为子图的n个顶点的图的边的最大数目就依赖于G的色数.因此TR.Jensen和B.Toft断言:图着色理论在离散数学中处于中心地位.在现实生活中许多领域都会涉及到将某种对象的集合按照一定的规划进行分类的问题,例如排课表问题、储存问题、任务分配、时间表问题、排序问题、电路安排等,都与图着色理论密切相关. 图着色是指对图中的顶点、边(对平面图而言还有面)等按照一定的规则进行分类.对象不同或规则不同,便有各式各样的着色,如点着色、边着色、全着色、强着色、邻强边着色、邻点可区别全着色、点可区别全着色、边面着色、完美着色等多种着色方式. 为了恰当地表示大型超网络、存储问题、时间安排和任务分配等研究课题中各元素之间的关系,图的着色理论作为一种可行的工具被自然的引入.由于其良好的应用背景,图的着色理论已成为现在图论领域中迅速发展的分支之一. 讨论着色问题时,一类特殊的图-临界图起着非常重要的作用.本文第一章研究全着色临界图,全着色临界图分为全着色点临界图和全着色边临界图,而我们着重分析全着色边临界图的结构性质,在文献[2]给出的结果的基础上,作进一步推广,得到了一般的结论. 第二章引入邻点可区别全着色.邻点可区别全着色是全着色理论的一个最新研究方向,张忠辅等人提出图的邻点可区别全着色这个概念,得到了若干结果,并提出了有关猜想:对于每个顶点个数至少是2的连通图G有: xat(G)≤△(G)+3.目前所知结果并不多,尚有许多未解决的问题.本文给出几类图的邻点可区别全着色,验证了邻点可区别全着色猜想.