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

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

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

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

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

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