论文部分内容阅读
在文献中张忠辅等提出了图的邻点可区别全染色的概念，即：设G是阶至少为2的连通简单图，k是正整数，f是V(G)∪E(G)到{1，2，…，k}的映射.对任意u∈V(G)，记C(u)={f(u)}∪{f(uv)|uv∈E(G)，v∈V(G)}.如果
(i)对任意uv，vw∈E(G)，u≠w，有f(uv)≠f(vw)；
(ii)对任意uv∈E(G)，有f(u)≠f(u)，f(u)≠f(uv)，f(v)≠f(uv)，则称f为G的k-正常全染色.进一步，如果f还满足
(iii)对任意uv∈E(G)，有C(u)≠C(v)，则称f为G的k-邻点可区别全染色(简记为k-AVDTC).称min{k|G有k-邻点可区别全染色}为G的邻点可区别全色数，记作χat(G).其中C(u)称为点u在f下的色集合.本文研究了1-树图的邻点可区别全染色，并给出了1-树图的邻点可区别全色数.
在本文第一章我们分别就本文所用的术语、记号和结论作出了总结.在第二章研究了单圈图的邻点可区别全染色，并给出其邻点可区别全色数.在第三章中，我们讨论了1-树图的邻点可区别全染色.在3.1节中给出了△(G)≤3的1-树图的邻点可区别全色数.用另一个归纳基础，在3.2节中给出了△(G)≥4的1-树图的邻点可区别全色数.主要结果如下：
定理对单圈图G有：△(G)+1，当E(G[V△])=Φ；χat(G)={△(G)+2，当E(G[V△])≠Φ且G≠K3；△(G)+3，当G=K3.其中V△={u|u∈V(G)，d(u)=△(G)}.
定理对1-树图G有：△(G)+1，当E(G[V△])=Φ；χat(G)={△(G)+2，当E(G[V△])≠Φ且G≠K3；.△(G)+3，当G=K3.其中V△={u|u∈V(G)，d(u)=△(G)}.