圖的廣義著色.pdf

1、鄭州大學(xué)博士學(xué)位論文圖的廣義著色姓名：楊愛峰申請學(xué)位級別：博士專業(yè)：基礎(chǔ)數(shù)學(xué)指導(dǎo)教師：林詒勛原晉江20040301根據(jù)定理3，我們可以設(shè)計一個解決直徑為2的圖的導(dǎo)出匹配2一劃分問題的多項式時間算法對于直徑為2的平面圖的導(dǎo)出匹配2一劃分問題，下面是一個比較簡單的刻劃定理4設(shè)G是一個直徑為2的平面圖則imp(G)=2當(dāng)且僅當(dāng)存在xy∈E(V)使得G[Ⅳ(和，訂)]和G一Ⅳ(協(xié)”))是1一正則的定理5設(shè)G和日是兩個圖則imp(G日)≥m“『掣

2、]，『牮])其中X為點色數(shù)定理6設(shè)G和日是兩個圖，其中G有完美匹配則imp(GH)≤maximp(G)，x∞))定理5和定理6的界是最好可能的，文中給出了許多緊例子定理7imp(Go鮑)=x(G)k一樹可以遞歸地定義為：(n)鞏，是一個k一樹；(b)禮1個頂點的k一樹可以通過把一個新頂點與仉個頂點的％一樹的一個玩的所有頂點相連得到圖G的樹寬【33，34]是指G是缸樹的一個子圖的最小整數(shù)k，記為TW(G)定理8對任一圖G有imp(G)≤T

3、W(G)1推論9對任一連通的弦圖G有imp(G)≤△(G)定理10設(shè)G是一個至少有4個頂點的2一樹則imp(G)=2當(dāng)且僅當(dāng)G同構(gòu)于一個梯型樹推論11設(shè)G是一個至少有4個頂點的極大外平面圖則imp(G)=2當(dāng)且僅當(dāng)G同構(gòu)于一個梯型路定理12設(shè)G是一個極大平面圖則imp(G)=2當(dāng)且僅當(dāng)G同構(gòu)于尬點蔭度不含圈的圖稱為一個森林或者一個無圈圖圖G有導(dǎo)出森林缸劃分是指V(G)存在劃分(K，K，，％)使得每個導(dǎo)出子圖G[吲是一個森林圖G的點蔭度【