论文部分内容阅读
以图的染色理论和因子分解理论作为应用背景,本硕士论文研究了图的线性荫度及线性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.