21934.幾類圖的線性蔭度和線性k蔭度

1、分類編號：密級：單位代碼：10065學號：1210050018天滓?guī)熫么骭掌研究生學位論文論文題目：幾類圖的線性蔭度和線性尼一蔭度學生姓名：何圣潔申請學位級別：理學碩士申請專業(yè)名稱：運籌學與控制論研究方向：指導教師姓名：論文提交日期：幾類圖的線性蔭度和線性忌一蔭度摘要圖的著色理論和分解理論在許多領(lǐng)域都有很重要的應用。圖的線性蔭度和線性缸蔭度是圖的著色理論和分解理論中兩個重要的概念，近三十年來在國內(nèi)外得到了廣泛的研究。一個圖G的線性缸森林

2、是圖G的一個子圖，其中，它的每個連通分支為長度最多為七的路。圖G的線性舡蔭度z釓(G)即為分解圖G的邊集E(G)所需要的線性七一森林的最小數(shù)目。圖G的線性缸蔭度的概念最早是由Habib和Peroche提出的，它是邊染色的自然推廣。顯然，一個線性1一森林就是一個匹配，2口1(G)就是圖G的邊色數(shù)，也即)(，(G)。當森林的每條路的長度沒有限制時，則圖G的邊集E(G)分解成這種森林的最小數(shù)目就是圖G的線性蔭度，記作fn(G)或者fn。(G)

3、。下面關(guān)于Zn七(G)的上界的猜想11是由Habib和Peroche在1982年提出的。猜想11∽≤，l精I]秈p卜Ⅳ∽州1’一Il幫l，秈(G)∽(G)Il，當七=Iy(G)I一1時，這就是Al【iy鋤a的猜想。猜想12zn(G)≤本文主要包括五章，其中第五章又分為兩節(jié)：在第一章中，介紹了預備知識和圖的線性蔭度和線性七蔭度的相關(guān)研究背景。第二章中，我們得到了m個圈ck的笛卡爾積圖c：【：：：的線性(佗一1)一蔭度的精確值。第三章中，我