關于圖的鄰點(強)可區(qū)別全染色的一些結果.pdf

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

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

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