论文部分内容阅读
图的染色问题是图论中一个非常重要的研究课题.图的染色理论的应用是比较广泛的,它在诸如计算机理论，网络设计，组合最优化，网络中的数据传输等方面都起着重要作用.它和我们日常生活也有着密切联系.例如，任务的调度，电路的布局，通讯系统的频道分配，化学品的存放问题，考试日程安排问题，课程与教室安排问题等都可以转化为图染色问题来解决。根据染色规则的不同或者对象的不同，图的染色可以分成许多种.本文主要讨论了全染色和点荫度。 本文中所有的图都是有限且非空的无向简单图.对于一个图G=(V,E)，我们分别用V(G)，E(G)，δ(G)和△(G)（或简单的用V,E，δ,△）来表示图G的点集，边集，最小度和最大度.当G是平面图时，用F(G)表示G的面集.分别用|V(G)|，|E(G)|和|F(G)|（或简单的用|V|，|E|和|F|）表示图G的顶点数，边数和面数.用d（f)表示面f的度数，即与f关联的边数;用d（v)表示点v的度数，即v的邻点的个数. 在第一章，我们对图染色理论的发展和本文要讨论的染色问题给出了比较完整的介绍.首先，我们介绍了一些图论中的基本概念与符号;其次，我们给出本文要研究的全染色和点荫度的详细定义以及与之相关的猜想与结论;然后，我们对本文采用的证明方法和思路进行说明;最后给出本文的主要结论. 在第二章，我们主要讨论全染色并给出三个结论及其证明.对于一个图G=(V,E)，它的一个正常k-全染色是指从V∪E到集合{1，2.…，k}的一个映射，使得G中任意两个相邻的点，相邻的边，以及相关联的点与边都分配到不同的颜色.如果一个图G存在一个正常的k-全染色，就称该图是k-全可染的.使得图G是k-全可染的最小整数k称为图G的全色数，记为x"(G).由定义我们可得知图G的全色数至少是△+1.Behzad与Vizing分别独立给出了著名的全染色猜想:对任意图G，都有x"(G)≤△+2.对于平面图，此猜想当△=6时还没有被证明.对于最大度比较大的平面图，我们可以得到它的一个精确值，即X"(G)=△+1.目前，这个结果已经被证明对于△≥9成立.对最大度△≤8的平面图加上一些限制条件时全色数也可以得到这个值.本文证明了在某些限制条件下的平面图的全色数是△+1. 本章第一个结论是:假设G是一个平面图且△≥7，如果G中不包含弦7-圈，那么G的全色数是△+1.本章第二个结论是:假设G是一个平面图且△=7，如果对G中每一个点v，都存在一个整数k∈{3，4，5，6，7，8}使得v不关联kv-圈，那么G的全色数是8.由此结论得到的一个推论是:假设G是一个平面图且△≥7，如果对G中每一个点v，都存在一个整数kv∈{3，4，5，6，7，8}使得v不关联kv-圈，那么G的全色数是△+1.证明时除了利用已有的一些禁用结构，我们还验证了一个新的禁用结构.本章第三个结论是:假设G是一个平面图且△≥7，如果G中没有相邻的拟-弦5-圈，那么G的全色数是△+1. 在第三章，我们讨论了平面图的点荫度.图G的一个森林k-着色是指从点集V(G)到集合{1，2，…，k}的一个映射，这个映射使得着同一种颜色的点集合导出一个无圈的子图，也就是森林.图G的点荫度va(G)指的是使G有一个森林k-着色的最小的k.点荫度的这个说法是1968年由Chartrand等人首次提出的.Chartrand等人指出对任意图G有va(G)≤[1+△(G)/2]且对任意平面图有va(G)≤3.第二年，Chartrand和Kronk又证明了对平面图的点荫度来说3这个界是紧的.如果对平面图所含的圈加入一些限制条件，点荫度可以降到2.本文主要讨论了平面图的点荫度.得到的第一个结论是:假设G是一个不含相交的5-圈的平面图，那么G的点荫度至多是2.证明这个结论时的难点在于禁用结构的证明比较困难.本章的第二个结论是:假设G是一个3-圈与4-圈不相邻且5-圈与5-圈不相邻的平面图，那么G的点荫度小于等于2. 在第四章中，我们介绍了一些与全染色和点荫度相关的染色，并介绍了其它一些可以考虑的图类.给出我们要继续努力的方向和需要考虑的问题.