论文部分内容阅读
图的染色理论起源于著名的的“四色猜想”,在图论研究中占有重要的地位.图的染色理论在最优化,计算机理论,网络设计等方面都有着重要的应用.本文主要讨论稀疏图的非正常染色问题.设k为正整数,φ是从图G的顶点集V(G)到颜色集合{1,2,···,k}的一个映射,如果对任意的1≤i≤k,染颜色i的顶点集所导出子图的最大度不超过di,则称φ是图G的一个(d1,d2,…,dk)-染色.显然如果d1=d2=…=dk=0,则φ是图G的一个正常k-染色.图G的最大平均度,记为mad(G),是指图G的所有子图的平均度的最大值.一般用最大平均度表示图的稠密程度.如果图G的最大平均度是常数,则称G是稀疏图.稀疏图的染色问题一直是图论学者关注的热点问题.2006年,Havet和Sereni证明了如果图G的最大平均度小于酱,则图G是(k,k)-可染的,Borodin等人在2010年证明了如果图G的最大平均度小于3k+4/k+2,则图G是(k,0)-可染的.在本文中,我们主要考虑稀疏图的(4,0)-染色和(k,0,0)-染色,改进了Borodin等人的结果.平面图的3-染色问题是平面图染色问题的热点,著名的Grotzsch定理指出不含三角形的平面图都是3-可染的,即(0,0,0)-可染的.1976年,Steinberg提出猜想：每个不含4-圈和5-圈的平面图是3-可染的.最近,王应前等人证明了不含4-圈和6-圈的平面图是(3,0,0)-可染的和(1,1,0)-可染的.本文主要讨论了稀疏图和平面图的非正常染色问题.我们通过三个章节介绍.第一章,首先介绍了图论中的一些基本概念,并给出了非正常染色问题的历史背景和发展,最后说明本文的主要结论.第二章研究了稀疏图的非正常染色问题,证明了：定理1.如果图G的最大平均度不超过警,则图G是(4,0)-可染的.定理2.如果图G的最大平均度不超过4k+9/k+3,则图G是(k,0,0)-可染的.此外,我们还构造图类说明定理1中最大平均度的界是紧的,同时构造了最大平均度为12k+14/3k+4的非(k,0,0)-可染的一类图.第三章我们对不含长度为4和5的圈和相交三角形的平面图的3-染色问题进行讨论,得到下面的结论：定理3.设G是不含长度为4和5的圈的平面图,如果G不含相交三角形,则G是(2,0,0)-可染的.