若干圖的關(guān)聯(lián)著色與鄰點(diǎn)可區(qū)別關(guān)聯(lián)著色研究.pdf

1、圖G的關(guān)聯(lián)著色是從關(guān)聯(lián)集I(G)到顏色集合C的一個(gè)映射σ,使得G中任何兩個(gè)相鄰關(guān)聯(lián)具有不同的象.若σ:I(G)→C是G的一個(gè)關(guān)聯(lián)著色且｜C｜=k,k是一個(gè)正整數(shù),則稱G是k-可關(guān)聯(lián)著色的,σ是G的一個(gè)k-關(guān)聯(lián)著色,使得G是k-可關(guān)聯(lián)著色的最小的k值稱為G的關(guān)聯(lián)色數(shù),記為χi(G),即χi(G)=min{|C|｜σ:I(G)→C是G的關(guān)聯(lián)著色}.
　　鄰點(diǎn)可區(qū)別關(guān)聯(lián)著色的定義是在關(guān)聯(lián)著色的基礎(chǔ)上推廣出來的,進(jìn)一步細(xì)化了圖的有關(guān)著色參

2、數(shù):若對任意uv∈(G)滿足Cu≠Cv,則稱σ為G的k-鄰點(diǎn)可區(qū)別關(guān)聯(lián)著色,并稱χai(G)=min{k|存在G的k-鄰點(diǎn)可區(qū)別關(guān)聯(lián)著色}為G的鄰點(diǎn)可區(qū)別關(guān)聯(lián)色數(shù).
　　本文研究了若干圖的關(guān)聯(lián)著色與鄰點(diǎn)可區(qū)別關(guān)聯(lián)著色,具體安排如下:
　　第二章,確定了循環(huán)圖Cn<1,n/2>的關(guān)聯(lián)色數(shù).
　　第三章,運(yùn)用反證、窮染等方法確定了兩類單圈圖的鄰點(diǎn)可區(qū)別關(guān)聯(lián)色數(shù).
　　第四章,確定了皇冠圖的鄰點(diǎn)可區(qū)別關(guān)聯(lián)色數(shù).