论文部分内容阅读
许多实际问题如时间表问题、分工表问题和运输问题都可化为图的染色问题。图的荫度理论是关于图的染色问题的理论。图的染色问题的研究是从图的点染色，如四色问题开始的。之后是图的边染色等问题。图的点染色就是把图的点集分解成一些互不相交的点独立集的方法。图的边染色就是把图的边集分解成一些互不相交的边独立集的方法。之后人们开始考虑是否可以把图的点集或边集分解成其他形式呢?自然先考虑的是树，这就产生了图的荫度理论。1970年，Harary[2]又提出了图的线性荫度这个概念。
1980年，Akiyama，Exoo和Harary[3]猜想：对任何正则图G，有
此后，著名的LAC猜想：对任何简单图G，有
极大地推动了对图的荫度理论的研究。
Habib和Peroche[4]进一步提出了线性k-荫度的概念，并给出了一个关于线性k-荫度的猜想：
猜想1.2.2[4]如果G是阶为n的图，且k≥2，那么
本论文以图的线性荫度和线性2-荫度为研究内容，主要沿着推广已有结论和探索新结果两个思路进行研究．主要分为以下四个部分：
第一章介绍了本文用到的定义、符号及专业术语，并回顾了荫度理论的发展历史。
第二章考虑图的线性2-荫度问题，介绍了几种特殊平面图的线性2-荫度问题。
第三章介绍了线性荫度研究的重要理论基础：权分配，及不含弦k-圈的平面图的线性荫度问题。
第四章我们考虑不含弦5-圈的平面图的线性2-荫度问题。得到了：
定理4.1 G是一个不含弦5-圈的平面图，。