一些特殊種類圖的[r,s,t]-著色.pdf

1、圖G的[r,s,t]-著色是對圖論經典著色的推廣.令G=(V,E)是頂點集為V,邊集為E的圖,給定非負整數r,s和t,圖G的[r,s,t]-著色是V(G)uE(G)到色集{0,1,…,k-1}的一個函數c,滿足:對于任意兩個相鄰的頂點vi,vj∈V,都有[c(vi)-c(uj)]≥r(稱為r條件r-condition);對于任意兩條相鄰的邊ei,ej∈E,都有[c(ei)-c(ej)]≥s(稱為s-條件s-condition);對于任意

2、一個頂點vi和與其關聯的邊ej,都有[c(vi)-c(ej)]≥t(稱為t-條件,t-condition)圖G的[r,s,t]-著色所用的最小色數k稱為圖G的[r,s,t]-色數,記作λr,s,t(G).本文主要研究了樹和含點不交偶圈的圖的[r,s,t]-色數與它們最大導出星的[r,s,t]-色數的關系.依據內容,本文分為五個部分:第一部分從歷史的角度,主要介紹了圖論的起源、發(fā)展及本文的選題背景.第二部分主要介紹了圖和點著色、邊著色、全

3、著色及其相關結論.第三部分主要介紹了[r,s,t]-著色的基本知識、研究現狀及相關引理.第四部分研究的是樹的[r,s,t]-色數.通過用樹TT的導出星K1,△(T)的一個[r,s,t]-著色對樹T進行點、邊著色,證明了樹的[r,s,t]-色數等于樹中最大導出星的[r,s,t]-色數.第五部分研究的是含點不交偶圈的圖的[r,s,t]-色數.通過用圖G的導出星K1,△(G)的一個[r,s,t]-著色對圖G進行從下往上著色,證明了含點不交偶圈