圖的廣義著色.pdf

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

2、]，『牮])其中X為點色數(shù)定理6設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設G是一個至少有4個頂點的2一樹則imp(G)=2當且僅當G同構于一個梯型樹推論11設G是一個至少有4個頂點的極大外平面圖則imp(G)=2當且僅當G同構于一個梯型路定理12設G是一個極大平面圖則imp(G)=2當且僅當G同構于尬點蔭度不含圈的圖稱為一個森林或者一個無圈圖圖G有導出森林缸劃分是指V(G)存在劃分(K，K，，％)使得每個導出子圖G[吲是一個森林圖G的點蔭度【