平面圖的鄰點(diǎn)可區(qū)別染色與點(diǎn)蔭度.pdf

1、圖的染色理論在圖論研究中占有重要的地位，其研究來源于著名的四色問題.染色理論在最優(yōu)化、計(jì)算機(jī)理論、網(wǎng)絡(luò)設(shè)計(jì)等方面都有著重要的應(yīng)用.
　　 設(shè)V(G)和E(G)是圖G的頂點(diǎn)集和邊集.記VE(G)=V(G)∪E(G)，并稱VE(G)中的點(diǎn)或邊為圖G的元素.圖G的一個(gè)k-全染色是從VE(G)到{1，2,...，k）的一個(gè)映射.圖G的k-全染色稱為是正常的，如果滿足相鄰或相關(guān)聯(lián)的兩個(gè)元素染不同色.使得圖G有正常k-全染色的最小整數(shù)k稱為

2、G的全色數(shù)，記為x"(G).類似的，我們可以定義圖G的正常點(diǎn)染色和正常邊染色，對應(yīng)的色數(shù)分別記為x(G)和x’(G).
　　 本文考慮加了某些限制條件的染色.對于一個(gè)全染色（不一定是正常的），如果它滿足任何一對相鄰的點(diǎn)鄰接的顏色集合不同，那么就稱這個(gè)染色是一般鄰點(diǎn)可區(qū)別全染色或gndt-染色.圖G存在gndt-染色所需要的最小顏色數(shù)稱為該圖的gndt-色數(shù)，記為gndt(G).對于一個(gè)k-gndt-染色，若再要求其是正常的全染色

3、，則稱這個(gè)染色是k-鄰點(diǎn)可區(qū)別全染色或者k-avd-全染色.圖G存在一個(gè)avd-全染色所需的最小顏色數(shù)稱為圖G的avd-全色數(shù)，記為x"a(G).類似的，我們可以定義k-鄰點(diǎn)可區(qū)別邊染色或者k-avd-染色.圖G存在一個(gè)avd-染色所需要的最小顏色數(shù)稱為圖G的avd-色數(shù)，記為x'a(G).圖G的點(diǎn)蔭度，記為va(G)，是滿足每個(gè)色類的導(dǎo)出子圖都是森林的圖G的點(diǎn)染色（非正常意義下）的最小顏色數(shù).本文共分四章進(jìn)行討論.
　　 第一

4、章介紹本文討論的問題的有關(guān)定義和發(fā)展現(xiàn)狀，并給出本文主要結(jié)果.
　　 第二章討論圖的鄰點(diǎn)可區(qū)別全染色.首先，我們討論圖的一般鄰點(diǎn)可區(qū)別全染色，并給出gndt(G)與x(G)之間的一個(gè)等式.其次，我們討論平面圖的鄰點(diǎn)可區(qū)別全染色.2005年，Zhang等人猜想:若G是階數(shù)至少為2的連通圖，則x"a(G)≤△+3.我們對最大度至少為11的平面圖，證明了這個(gè)猜想成立.同時(shí)，我們還刻畫了高度平面圖的鄰點(diǎn)可區(qū)別全染色，得到了以下結(jié)果:若平

5、面圖G滿足△≥14，則△+1≤x"a(G)≤△+2;并且x"a(G)=△+2當(dāng)且僅當(dāng)G包含兩個(gè)相鄰最大度頂點(diǎn).
　　 第三章討論圖的鄰點(diǎn)可區(qū)別邊染色.2002年，Zhang等人猜想:若G是階數(shù)至少為3的連通圖且G≠C5，則△≤x'a(G)≤△+2.我們證明了，最大度至少為12的平面圖滿足這個(gè)猜想.
　　 第四章討論圖的點(diǎn)蔭度.眾所周知，任意平面圖的點(diǎn)蔭度至多為3，并且存在點(diǎn)蔭度為3的平面圖.因此，對平面圖G，尋找va(G