论文部分内容阅读
设图G是阶至少为2的连通图,k是正整数,σ是从V(G)∪E(G)到{1,2,…,k}的映射。若 (ⅰ)对任意uv,vw∈E(G),u≠w,有σ(uv)≠σ(vw); (ⅱ)对任意uv∈E(G),有σ(u)≠σ(v),σ(u)≠σ(uv),σ(v)≠σ(uv);则称σ为G的一个k-正常全染色。 进一步,对任意u∈V(G),记σ[u]={σ(u)}∪{σ(uv)|uv∈E(G),v∈V(G)},如果σ还满足 (ⅲ)对任意uv∈E(G),有σ[u]≠σ[v];则称σ为G的一个k-邻点可区别全染色(Adjacent Vertex Distinguishing Total Coloring),简记为k-AVDTC,称 χat(G)=min{k|G有k-邻点可区别全染色}为G的邻点可区别全色数。 本文研究了若干图类的邻点可区别全染色。我们在第二章中确定了花图的邻点可区别全色数:当r=3,m=1或n-2m-1=0时,花图Fr,m,n的邻点可区别全色数等于最大度加2,在其它情况下,花图的邻点可区别全色数等于最大度加1。在第三章和第四章中我们分别确定了Halin图和1-树图的邻点可区别全色数:设G是Δ(G)≥5的Halin图,且对任意v∈I(G),d(v)≥4,记T=G-E(f0)且Δ(T)=Δ(G),当E(T[VΔ])=φ时,χat(G)=Δ(G)+1;当E(T[VΔ])≠φ时,χat(G)=Δ(G)+2。对于Δ(G)≥4的1-树图,当E(G[VΔ])=φ时,χat(G)=Δ(G)+1;当E(G[VΔ])≠φ时,χat(G)=Δ(G)+2。在第五章中我们从系列平行图的结构性质出发,利用穷染法,数学归纳法以及换色技巧研究了低度系列平行图的邻点可区别全染色:对于Δ=5,6,7的SP图G,当E(G[VΔ])=φ时,χat(G)=Δ(G)+1;当E(G[VΔ])≠φ时,χat(G)≤Δ(G)+3。