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

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

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

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