關(guān)于圖的鄰點(diǎn)(強(qiáng))可區(qū)別全染色的一些結(jié)果.pdf

1、本文所討論的圖均為有限無(wú)向的簡(jiǎn)單連通圖.
　　 圖的染色問(wèn)題是圖論研究的經(jīng)典領(lǐng)域.張忠輔等人在全染色的基礎(chǔ)上,提出了鄰點(diǎn)可區(qū)別全染色和鄰點(diǎn)強(qiáng)可區(qū)別全染色的概念.設(shè)G(V,E)為階不小于2的簡(jiǎn)單連通圖,k為正整數(shù),.(f)是V(G)∪E(G)到{1,2,…,k)的映射,滿足:對(duì)任意的(u)υ∈E(G),(f)(u)≠(f)(υ),(f)(u)≠.(f)(uυ),(f)(υ)≠(f)(uυ)；對(duì)任意的(u)υ,(u)w∈E(G)(υ

2、≠w),(f)(uυ)≠,(υW)；對(duì)任意的uυ∈E(G),C(u)≠C(υ),其中C(u)={(f)(u)}∪{(f)(uυ)｜uυ∈E(G),υ∈y(G)),那么稱(f)為圖G的一個(gè)鄰點(diǎn)可區(qū)別全染色,簡(jiǎn)記為k-AVDTC,且稱Xat(G)=min{k｜G有k-AVDTC}為G的鄰點(diǎn)可區(qū)別全色數(shù).若將上述C(u)改為C(u)={(f)(u)}∪{(f)(υ)｜uυ∈E(G),υ∈V(G)}∪{(f)(uυ)｜uυ∈E(G),υ∈V(G

3、)},其余條件不變,此時(shí)稱(f)為圖G的一個(gè)鄰點(diǎn)強(qiáng)可區(qū)別全染色,簡(jiǎn)記為k-AVSDTC,且稱Xast(G)=min{k｜G有k-AVSDTC)為G的鄰點(diǎn)強(qiáng)可區(qū)別全色數(shù).
　　 張忠輔等人討論了一些特殊圖如圈,完全圖,完全二部圖,樹(shù)等的鄰點(diǎn)可區(qū)別全色數(shù)和鄰點(diǎn)強(qiáng)可區(qū)別全色數(shù),并提出猜想:(1)對(duì)于階數(shù)不小于2的簡(jiǎn)單圖G,Xat(G)≤△(G)+3；(2)若G是最大度為△的平面圖,則Xast(G)≤△(G)+3.
　　 在本文