1.2 国内外研究现状与发展趋势

图的荫度理论是从图的着色问题中产生的，但在图论尚未正式建立的时候，由于它具有及其重要的理论意义和实践意义，图的着色问题已经被提出来并广泛的运用于在实际生活中的研究和发展。关于图的着色问题，人们最早研究的是图的点着色，点着色起源于1852年，首先是由英国青年学生Francis Guthrie 提出来的四色猜想问题。其中四色猜想具体是在地图上的各个国家至多只需要4种颜色来染色，从而能使得任何具有共同边界的两个国家染的颜色都不相同。从此四色问题就成为图论中最困难的问题之一，直到1976年才被美国的Appel和Haken证明四色猜想成立，他们是用借助高速计算机证明的。

关于图的点染色问题，至今已得到了极大的发展，以下做出简单的介绍。

图的点着色问题中最著名的四色定理，就是给定图 , 让他的顶点进行着色，从而使得任何相邻两点染不同的颜色，我们称这种染色方式为正常点着色，得到图 有正常点着色的最少颜色数，称为 的点色数，用 来表示，因此可以把四色定理总结成以下一些定理：

定理1[1]. 若图 是平面图，则 。

Books在1941年给出了下面著名的定理：

定理2[1]. 若图 是且它不是奇圈也不是完全图的连通的简单图，则 。 给定图 ，对它的边进行着色，让任何相邻两条边着不同的颜色。称这种着色为正常边着色，从而得图 有正常边着色的最少颜色数，称为 的边数，用 来表示。对于图的边着色，有如以下一些著名的Vizing定理：

定理3[1]. 对任何简单图 ，有 。

简而言之，图的点着色就是把图的点集分解为若干个互不相交的点独立集的并，图的边着色就是把图的边集分解成若干个互不相交的边独立集的并，因此，人们就考虑是否可以用其他的形式将图的点分解或边分解呢？自然而然人们首先想到了树，于是就产生了图的荫度理论。

1970年，Harary 提出了图的线性荫度这个概念。

    Harary提出了图的线性荫度理论之后，1980年，Akiyama对线性荫度理论提出了下面的猜想：

猜想1.2.1[2] 对于任何正则图 , 则 。

同时他们还给出了树，完全图，完全二分图的线性荫度理论，并证明了 时猜想成立，在[3]中他们并证明了 时猜想成立。 Enomoto等证明了 时猜想成立。之后，Guldan证明了对 时猜想成立。

由于对任何图 有 和对于任何正则图 有 ，所以猜想1.2.1等价于以下的猜想（著名的LAC猜想）：

猜想1.2.2（LAC）对任何简单图 ，有 。

吴建良[4]证明了此猜想对于 的平面图成立。

定理1.2.1[4] 如果 是平面图，且 ，那么 。

在[5]中，他又证明了 时，猜想也成立。

定理 1.2.2[5] 如果 是平面图，且 ，那么 。

Alon[6]考虑了围长比较大的图的线性荫度理论，证明：对每个 ，当 充分大的时有 ；尤其是 为偶数（奇数），且围长 （或 ），那么LAC猜想成立。

    吴建良在文献[7]中研究笛卡尔图的线性荫度得到以下定理：

定理1.2.3[7] 若 为偶数且 , 则 ；

定理1.2.4[7] 若 和 ，则 ：

    2001年，Alon研究正则图的线性 荫度，得到更好的上界：

定理1.2.5[6] 存在常数 , 使得对任意 正则图有

 。

Culdan给出了线性荫度的一个上界： 

吴建良在[7]中给出：

定理1.2.6[7] 对完全二分图 ， ，有 

其中 。

定理1.2.7[7] 设 和 为任意两个图和 ，则  几类特殊图形的线性2-荫度(2):http://www.751com.cn/shuxue/lunwen_44661.html