設(shè)G是一個簡單圖.圖G的一個正常kk-點染色是指用kk種顏色對G的頂點的進(jìn)行分配,使得任意兩個相鄰的頂點都分配到不同的顏色.圖G的染色數(shù)是指使G為k-點染色的數(shù)k的最小值,用χ（G）表示.一個無孤立點的圖G的全控制集是指G的一個頂點子集S,使得G的每個點至少與S中的一個頂點相鄰.圖G的全控制數(shù)γt（G）是指G的一個最小全控制集的基數(shù).結(jié)合圖的點染色和全控制集的概念,Kazemi給出了一個新的研究變量——全控制染色,其定義如下:令G是一個無孤立點圖,圖G的一個全控制染色是指G的一個正常點染色,使得G的每個點與某個色類的所有點相鄰.G的全控制染色數(shù)是指使G存在全控制染色的最小顏色數(shù)目,用χdt（G）表示.對于全控制染色的研究有如下結(jié)果.2015年,Kazemi等人得到一個點數(shù)為n的無孤立點的連通圖G的全控制染色數(shù)界于2到n之間,即2≤χdt（G）≤ n.同時,他們刻畫了全控制染色數(shù)為2和n的圖類.在同一文獻(xiàn)中,Kazemi等人證明了確定圖的全控制染色數(shù)是NP-困難的.最近,Bagan等人設(shè)計了一個關(guān)于P4-稀疏圖上的全控制染色數(shù)的多項式時間算法.本論文共分為四章,主要研究了特殊圖上的全控制... 

【文章來源】：山東師范大學(xué)山東省

【文章頁數(shù)】：37 頁

【學(xué)位級別】：碩士

【部分圖文】：

從左到右依次是:

：Ｙ?Ｔ?ｔ?ｆ??圖３．點數(shù)為２的準(zhǔn)海星圖．從左到右依次是：Ｐ４，叉子圖，戶，Ｐ，風(fēng)箏圖．??當(dāng)我們考慮準(zhǔn)海膽圖和準(zhǔn)海星圖時，有下面１０種形式．我們稱類型１（或類型２）海膽圖（或海星圖）；類型３（或類型４）為海膽圖（或海星圖），是將海膽圖（或海星圖）體中的一個點用欠２來代替；類型５（或類型６）為海膽圖（或海星圖），是將海膽圖（或星圖）身體中的一個點用《５２來代替；類型７（或類型８）為海膽圖（或海星圖），是將海圖（或海星圖）腿中的一個點用來代替；類型９（或類型１０）為海膽圖（或海星圖），將海膽圖（或海星圖）腿中的一個點用＆來代替；在這里，我們要求奇類型的Ｃ和Ｓ的點數(shù)至少為３．?＂??令＾?＝?（Ｋ，＾），Ｇ２?＝?〇／２，五２）是兩個圖，其中Ｒ?ｎ＼／２?＝?０，?可分離的劃分為（Ｒ１，片）？考慮這樣一個圖，它的點集是Ｖｘ?Ｕ?Ｖ２，邊集是禺Ｕ?Ｅ２?Ｕ?｛砂卜ｅ我們把這類圖用＜＾乂６２表示．下面是這類圖操作的一個例子（見圖４）．??

當(dāng)我們考慮準(zhǔn)海膽圖和準(zhǔn)海星圖時，有下面１０種形式．我們稱類型１（或類型２）為??海膽圖（或海星圖）；類型３（或類型４）為海膽圖（或海星圖），是將海膽圖（或海星圖）身??體中的一個點用欠２來代替；類型５（或類型６）為海膽圖（或海星圖），是將海膽圖（或海??星圖）身體中的一個點用《５２來代替；類型７（或類型８）為海膽圖（或海星圖），是將海膽??圖（或海星圖）腿中的一個點用來代替；類型９（或類型１０）為海膽圖（或海星圖），是??將海膽圖（或海星圖）腿中的一個點用＆來代替；在這里，我們要求奇類型的Ｃ和Ｓ中??的點數(shù)至少為３．?＂??令＾?＝?（Ｋ，＾），Ｇ２?＝?〇／２，五２）是兩個圖，其中Ｒ?ｎ＼／２?＝?０，?可分離的，??劃分為（Ｒ１，片）？考慮這樣一個圖，它的點集是Ｖｘ?Ｕ?Ｖ２，邊集是禺Ｕ?Ｅ２?Ｕ?｛砂卜ｅ??我們把這類圖用＜＾乂６２表示．下面是這類圖操作的一個例子（見圖４）．??？?？?？?？?？?？?？??？??Ｘ??圖４．從左到右依次是：??


本文編號：3501537