圖的廣義著色.pdf

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

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

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