论文部分内容阅读
图的染色问题起源于地图的染色问题,即著名的四色猜想:每幅地图都可以用四种颜色着色,并且相邻的国家所染颜色不同.数学家赫伍德首先证明了五色定理,得出每张地图都能用五种或者更少的颜色染色.随后,关于四色猜想的证明出现了很多版本,但是过程都很繁琐.直到1976年6月,美国数学家Appel和Haken经过四年的艰苦工作,终于用计算机完成了对四色猜想的证明,四色猜想改称为四色定理.但是,很多数学家并没有满足于计算机取得的现有成就,他们更希望得到一种简单到可以通过书面表达的证明方法.这个想法目前尚未实现. 图的染色问题作为图论研宄的一个重要分支,在实际生活中有着广泛的应用.而图的线性荫度和线性fc-荫度问题作为图的边染色问题的一种,在图的分解方面有着重要的研宄意义.给定一个图G,若G可以被划分为m个边互不相交的线性森林,则称最小整数m为图G的线性荫度,记为la(G);若G可以被划分m个边互不相交的线性fc-森林,则称最小整数m为图G的线性fc-荫度,记为^(G). 近年来,图的荫度问题得到了广泛的研宄,但是关于图的线性fc-荫度的研宄却相对较少.本论文在已有研宄结果的基础上,对图的线性荫度和线fc-荫度(fc=2时)两种问题进行新的研宄.论文的主要内容分为以下四个部分: 第一章,介绍了论文涉及的一些基本概念和符号的定义以及图的线性荫度和线性fc-荫度问题的产生和发展,并且给出了本论文得到的主要结果. 第二章,研宄不含连续三个3-面的可平面图的线性荫度问题.首先,利用图的线性染色理论对fc-删除-极小图的结构性质进行了研宄,然后运用权转移方法证明了不含连续三个3-面的可平面图的线性荫度满足la(G)<4,当A(G)<8时. 第三章,研宄具有性质Pk的图类的线性2-荫度问题.通过对所研宄的图类进行边划分得到相关的结构引理,进而在已有结论的基础上完成了对本章主要结论的证明.最后,运用所得结果改进了一些可平面图的线性2-荫度的上界. 第四章,总结部分.对论文中有进一步研宄空间和意义的问题做了详细的说明与展望.