论文部分内容阅读
以图的染色理论和因子分解理论作为应用背景，本硕士论文研究了图的线性荫度及线性2-荫度问题.这两个概念在图的染色及分解方面有着重要的应用.关于图的线性荫度，近20年来在国内外得到了广泛研究，但对图的线性2-荫度问题研究的不多.
设la(G)，la2(G)，△(G)分别表示图G的线性荫度，线性2-荫度和最大度.本领域存在着著名的线性荫度猜想：
猜想对任何简单图G，有[△(G)2]≤la(G)≤[△(G)+12].
在第二章，我们考虑了平面图的线性荫度问题.给出了不含弦-k-圈(4≤k≤6)的平面图的结构性质，并且证明了每个△=7且不含弦-k-圈(4≤k≤6)的平面图均满足线性荫度猜想.
在第三章，我们考虑图的线性2-荫度问题.研究了K4-minor-free图、Halin图、不含4-圈的平面图的线性2-荫度问题.得到了：(1)对最大度为△(G)的K4-minor-free图，有la2(G)≤△(G)+52.
(2)若G为一个Halin图且G=T∪C，有{=3,3≤△(G)≤5;la2(G){≤4,△(G)=6;{=la2(T),△(G)≥7.
(3)设G为不含4-圈的平面图，则la2(G)≤[△(G)+12]+3.