圖的[r,s,t]-染色.pdf

1、設(shè)圖G=(V(G)，E(G))是簡(jiǎn)單圖，其中V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集.令△(G）是圖G的最大度.
　　給定非負(fù)整數(shù)r，s和t，圖G=(V(G)，E(G))的[r,s，t]-染色指的是映射c:V(G)∪E(G)→{0，1,…，k-1}，使得圖G中任意相鄰的兩個(gè)頂點(diǎn)vi，vj滿(mǎn)足|c（vi）-c(vj)|≥r;任意兩條相鄰的邊ei，ej滿(mǎn)足|c(ei)-c(ej)|≥s;并且任意頂點(diǎn)vi和與其關(guān)聯(lián)的邊ej滿(mǎn)足|c（

2、vi）-c(ej)|≥t.使得圖G存在[r，s，t]-染色的最小正整數(shù)k稱(chēng)為[r，s，t]-染色數(shù)，記作Xr，s，t(G).顯然，[1，0，0]-染色是點(diǎn)染色，[0，1，0]-染色是邊染色，[1，1，1]-染色是全染色.由于[r，s，t]-染色是點(diǎn)染色，邊染色以及全染色的結(jié)合與推廣，并且參數(shù)r，s，t之間的大小關(guān)系也很復(fù)雜.因此，[r s，t]-染色問(wèn)題的研究有一定的難度.目前，[r，s，t]-染色的研究主要集中在兩個(gè)方面:一是對(duì)某類(lèi)圖

3、的[t，s，t]-染色進(jìn)行研究;二是限定參數(shù)r，s，t的值對(duì)圖G的[r，s，t]-染色進(jìn)行研究.本文就輪圖以及與輪圖相關(guān)的幾類(lèi)圖的[r s，t]-染色展開(kāi)了研究:
　　(1)確定了友誼圖C(n)3的[r，s，t]-染色數(shù)的值和界.
　　(2)討論了當(dāng)m為不小于3的奇數(shù)時(shí)，Jahangir圖Jn,m的[r，s，t]-染色.首先給出了當(dāng)min{r, s，t}=0時(shí)，Jahangir圖Jn，m的[r，s，t]-染色數(shù)的值與界.當(dāng)m

4、in{r, s，t}≥1時(shí)，分別給出了n為奇數(shù)時(shí)以及n為偶數(shù)時(shí)，Jn,m的[t，s，t]-染色數(shù)的值與上界.
　　(3)研究了輪圖Wn以及多輪圖NWn的[r，s，t]-染色.首先證明了當(dāng)min{r，s，t}=0時(shí)，以及當(dāng)min{r，s，t}≥1且△(NW2n)≥6時(shí)，NW2n的[r，s，t]-染色數(shù)等于其生成友誼圖C(Nn)3的h，s，t]-染色數(shù).然后確定了當(dāng)r≥1，s≥1，1≤t≤2s時(shí)，偶輪圖W4的[r，s，t]-染色數(shù)的值

5、與上界.最后給出了△（NW2n+1）≥5的多奇輪圖NWn+1的[r，s，t]-染色數(shù)的值與界.
　　(4)確定了扇圖Fn以及多扇圖NFn的[r，s，t]-染色數(shù)的值與界.首先給出了當(dāng)min{r，s，t}=0時(shí)，扇圖Fn以及多扇圖NFn的[r，s，t]-染色數(shù)的值與界.其次證明了當(dāng)min{r，s，t}=0時(shí)，以及當(dāng)min{r，s，t}≥1，△(NF2n)≥6;和△（F2n）=4且s≥t，或s＜t≤2s與r＞s+t時(shí)，多偶扇圖NF2n