關(guān)于圖的關(guān)聯(lián)色數(shù).pdf

1、對于圖G，稱I(G)={(v，e)∈V(G)×E(G)｜v與e相關(guān)聯(lián)}為G的關(guān)聯(lián)集，說G的兩個關(guān)聯(lián)(v，e)和(w，f)是相鄰的，當(dāng)且僅當(dāng)下列三種情況之一成立： (1)v=w；(2)e=f；(3)vw=e或vw=f. 圖G的一個關(guān)聯(lián)著色是從關(guān)聯(lián)集I(G)到顏色集C的一個影射π，使得I(G)中任何兩個相鄰的元素都有不同的像。若π：I(G)→C是G的關(guān)聯(lián)著色，且|C|=k，k是一個正整數(shù)，則稱G是k-可關(guān)聯(lián)著色的。映射π是圖

2、G的一個關(guān)聯(lián)著色，使得G是k-可關(guān)聯(lián)著色的最小的k埴稱為G的關(guān)聯(lián)色數(shù)。 本文主要研究了圖的關(guān)聯(lián)色數(shù)。第二章確定了兩類平面圖(花圖和棱柱)的關(guān)聯(lián)色數(shù)：花圖的關(guān)聯(lián)色數(shù)等于其最大度加1；對于棱柱Qn(n≥3)，當(dāng)n≡0(mod5)時，棱柱的關(guān)聯(lián)色數(shù)等于其最大度加1，當(dāng)是其它情況時，棱柱的關(guān)聯(lián)色數(shù)等于其最大度加2。第三章首先給出了圖與其Mycielski圖關(guān)聯(lián)色數(shù)的關(guān)系：對于任意n階圖G，如果它的關(guān)聯(lián)色數(shù)等于其最大度加1，那么當(dāng)它的最大

3、度的2倍不等于n時，M(G)的關(guān)聯(lián)色數(shù)等于△(M(G))+1，當(dāng)它的最大度的2倍等于n時，M(G)的關(guān)聯(lián)色數(shù)小于等于△(M(G))+2；其次還研究了樹，最大度△≥5的Halin圖，完全二部圖的Mycielski圖的關(guān)聯(lián)色數(shù)：設(shè)T為最大度△≥3的樹，則M(T)的關(guān)聯(lián)色數(shù)等于△(M(T))+1；G為最大度△≥5的Halin圖，則M(G)的關(guān)聯(lián)色數(shù)等于△(M(G))+1；對于完全二部圖Km、n(m，n≥2)，則M(Km，n)的關(guān)聯(lián)色數(shù)的關(guān)聯(lián)色