圖的Cartesian積與合成的鄰點(diǎn)可區(qū)別E-全染色.pdf

1、設(shè)G=(V，E)是簡(jiǎn)單,無向,有限圖.
　　圖G的一個(gè)k全染色是指用k種顏色1,2,···,k對(duì)圖G的頂點(diǎn)和邊的一種分配.設(shè)f是圖G的一個(gè)k全染色,并且滿足相鄰頂點(diǎn)所染顏色不同,任一頂點(diǎn)的顏色與它的關(guān)聯(lián)邊的顏色也不同,則稱f是圖G的一個(gè)使用了k種顏色的E?全染色,進(jìn)一步,考慮這樣一種染色f,對(duì)任意的頂點(diǎn)u∈ V(G),用C(u)表示分配給頂點(diǎn)u以及u的所有關(guān)聯(lián)邊的顏色構(gòu)成的集合.對(duì)于G的任意兩個(gè)相鄰的頂點(diǎn)u和v,如果C(u)?=C

2、(v),那么稱f是圖G的一個(gè)使用了k種顏色的鄰點(diǎn)可區(qū)別E?全染色(簡(jiǎn)記為k?AVDETC).對(duì)圖G的一個(gè)鄰點(diǎn)可區(qū)別E?全染色所需要的最小的正整數(shù)叫做G的鄰點(diǎn)可區(qū)別E全色數(shù),記為χeat(G).
　　第二章,運(yùn)用分析法和構(gòu)造具體染色的方法,討論了針對(duì)點(diǎn)色數(shù)至少為2及鄰點(diǎn)可區(qū)別E全色數(shù)為3,4的簡(jiǎn)單圖來說,它們的Cartesian積圖的鄰點(diǎn)可區(qū)別E?全色數(shù).
　　第三章,運(yùn)用組合分析法及構(gòu)造具體染色的方法,討論了滿足某些條件的兩