论文摘要
图论起源于18世纪,最早关于图论的文章是在1736年由Euler完成的,这篇文章用图的方法解决了著名的哥尼斯堡七桥问题.自二十世纪五十年代以来,由于计算机科学的迅速发展,有力地推动了图论的发展,关于图论方面的结果大量涌现.四色猜想作为图的染色问题的起源,一直引领着图论的发展,并使得图的染色理论成为图论中的一个重要分支.图的染色理论在最优化、计算机理论、网络设计、时间表问题等方面都有着重要的应用.本文主要讨论图的几类染色问题,如图的线性荫度、均匀染色及全染色等.本文所考虑的图都是有限简单图.给了一个平面图G,我们用V（G）,E（G）,F（G）和△（G）分别表示图G的顶点集,边集,面集及最大度.给了一个实数x,[x]和[x]分别表示不小于χ的最小整数和不超过χ的最大整数.图G的正常κ-全染色是指用κ种颜色对V（G）∪E（G）中的元素进行染色,使得相邻的或者相关联的两个元素染不同的颜色.使得图G存在正常的κ-全染色的最小正整数κ称为G的全色数,记作χ"（G）.类似地,如果我们只对图G的顶点（边）染色,那么就可以得到图G的点色数χ（G）（边色数χ’（G））.一个线性森林是每一个极大连通分支均为路的图.对于一个图G,φ是从E（G）到{1,2,…,t}的映射.若对任意α,1≤α≤t,均有染α色的边的导出子图是一个线性森林,则称φ为图G的一个线性t-染色.图的线性荫度是使得G有一个线性t-染色的最小t值,记为la（G）.此定义由Harary于1970年提出.下面是一个著名的线性荫度猜想：猜想1.对任何简单图G,均有[（?）]≤la（G）≤[（?）].Peroche证明了：即使△（G）=4,确定图G的线性荫度也是一个NP-困难问题.本文第二章主要给出了一些平面图的线性荫度的确切值.本文讨论的另一个问题是均匀染色.设φ是图G的一个正常κ-点染色,若（?）的任何两种不同颜色所染的顶点数目至多差1,则称（?）是G的一个均匀κ-染色.若G有一个均匀κ-染色,则称G是均匀κ-可染的.图G具有均匀κ-染色的最小正整数κ,称为G的均匀色数,记为Xe（G）.1973年,Meyer提出以下猜想（均匀染色猜想）：猜想2.如果G是不为完全图和奇圈的连通图,则χe（G）≤Δ（G）.1994年,Chen,Li和Wu提出了以下猜想：猜想3.如果G是一个连通图,且既不是完全图Kn,奇圈又不是完全二部图K2n+1,2n+1（n≥1）,那么G是均匀△（G）-可染的.本文将给出关于猜想3的几个结果.对于全染色,Behzad和Vizing分别提出以下猜想：猜想4.（全染色猜想）对任意图G,都有△（G）+1≤X″（G）≤△（G）+2.该猜想目前还远没有解决,对于平面图G,如果最大度△（G）≠6,则该猜想已经被验证.另外当G为一个平面图且△（G）≥9时,X″（G）=△（G）+1.本文将会讨论△（G）≤8时,几类有限制条件的平面图的全色数.本文共分四章.在第一章,我们介绍了图论中的一些定义、符号、本文所讨论的各种染色的进展状况及本文的主要结论,给出了一个简短但相对完整的综述.在第二章,我们讨论了平面图的线性荫度.求得了几类有限制条件的平面图的线性荫度的确切值,以下是本章的主要结果：结论1假设G是一个△（G）≥5的平面图.如果G不含5-圈和6-圈,则la（G）=[（?）].结论2令i和j是两个固定的正整数（3≤i≤j≤5）.若G是一个△（G）≥7的平面图,且G中任意i-圈和j-圈均不相邻,则la（G）=[（?）].结论3令G是一个△（G）≥5的平面图.若G中每一个4-圈均不与i-圈相邻（Vi∈{3,4,5}）,则la（G）=[（?）].在第三章,我们讨论了平面图的均匀染色.利用平面图的结构性质及换色法等技巧,改进了zhang和Yap的关于平面图均匀染色的结果.以下是本章的主要结果：结论4若G是最大度△≥10的平面图,则对任意的正整数m≥△,图G都是均匀m-可染的.结论5若G是最大度△≥6且不含3-圈的平面图,则对任意的正整数m≥△,G是均匀m-可染的.结论6若G是最大度△≥7且不含4-圈的平面图,则对任意的正整数m≥△,G是均匀m-可染的.在第四章,我们讨论了平面图的全染色.我们给出了有限制条件的两类平面图的全色数的精确值.以下是本章的结果：结论7假设G是一个不含相邻4-圈的平面图.如果△≥8,那么X″（G）=△+1.结论8假设G是一个△（G）≥6且不含相交4-圈的平面图,且G满足下列条件之一：（1）不含相交3-圈,（2）不含5-圈,（3）不含6-圈,则全色数X″（G）=△+1.
论文目录
相关论文文献
- [1].最大度大于等于7的平面图的线性荫度[J]. 运筹学学报 2020(03)
- [2].6-圈至多含一弦平面图的线性荫度[J]. 运筹学学报 2019(02)
- [3].三正则图的列表线性荫度(英文)[J]. 新疆大学学报(自然科学版) 2009(03)
- [4].可嵌入到欧拉示性数非负的曲面图的线性荫度[J]. 山东大学学报(理学版) 2018(12)
- [5].上可嵌入图与次上可嵌入图的线性荫度[J]. 华东师范大学学报(自然科学版) 2015(01)
- [6].某些图的线性荫度问题[J]. 河南工程学院学报(自然科学版) 2010(04)
- [7].笛卡尔积图的线性荫度(英文)[J]. Journal of Southeast University(English Edition) 2013(02)
- [8].平面图的各种染色综述[J]. 广州大学学报(自然科学版) 2019(05)