论文部分内容阅读
图的染色问题是图论研究中的一个热点话题.早在1965年M.Behzad就提出了全染色的概念,全染色是指对图G的顶点和边同时进行染色,使得任意相邻或相关联的元素(顶点和边)均染有不同的颜色,全染色所用的最少的颜色数就是图G的全色数.张忠辅等人在全染色的基础上,提出了邻点可区别全染色和邻点强可区别全染色的概念.而在本文中,提出了一种新的染色概念,称为第二类邻点可区别全染色.本文共有四章内容,主要研究了θk-图的第二类邻点可区别全染色数.
第一章给出了文中用到的相关符号,基本概念,相关结论以及给出了第二类邻点可区别全染色的概念.其内容为:
设图G=(V,E)是一个阶至少为3的连通简单图,k是一个正整数,f是V(G)∪E(G)到{1,2,…,k}的映射,对任意的u∈V(G),若uv∈E(G),则u关于v的色集合记为Cv(u)={f(u)}∪{f(v)}∪{f(uw)| uw∈E(G),w∈V(G)},如果
(1)对任意的uv,vw∈E(G),u≠w,有,f(uv)≠f(vw);
(2)对任意的uv∈E(G),有,f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);
(3)对任意的uv∈E(G),有Cv(u)≠Cu(v);
则称f是G的k-第二类邻点可区别全染色(Second—adjacent—vertex-distinguishing total coloring)(简记为k-SAVDTC).称min{k|G有k-SAVDTC}为G的第二类邻点可区别全色数,记作(x)(G).
第二章主要研究了θk-图的第二类邻点可区别全染色数,给出了本文的主要定理及其详细的证明过程.第三章则是讨论了与θk-图相关的图,即它的其中一类收缩图的第二类邻点可区别全染色数,同时给出了相关的结论.在第四章中给出了一些进一步可以探讨的问题.