论文部分内容阅读
染色问题一直是图论中的热点话题之一，它在组合分析和实际中有着非常广泛的应用，比如时间表问题、贮藏问题及电网络问题等．
本文分为四章，主要研究了图的全染色及邻点可区别全染色．
第一章对本文所用的术语、记号和结论作了总结．
第二章主要研究了一种特殊联图的全染色．全染色的概念是Behzad M.在1965年提出的．全染色是指对图G的顶点和边同时染色，使得任意相邻或相关联的元素(顶点和边)均染有不同的颜色；全染色所用颜色的最少数目称为图G的全色数，记为Xт(G)．之后，Behzad又提出了全染色猜想：对于任意简单图G，有Xт(G)≤△(G)+2．SSnchez-Arroyo[25]证明了判断Xт(G)=△(G)+1是NP-完全的．目前已经证明了全染色猜想对于一些特殊的图族是成立的，包括完全r-部图，最大度至少是8的平面图．本章根据联图的结构和全染色的定义，得到了联图C<,n> V K<,n>的全色数．从而证明了全染色猜想在这种特殊联图中的正确性．
第三章和第四章主要研究了两种联图的邻点可区别全染色．邻点可区别全染色的定义是张忠辅在2004年提出来的，其内容为：设G是阶至少为2的简单连通图，k是正整数， f是V(G)U E(G)到{1，2，…，k)的映射，对任意u∈V(G)，记C(u)={f(u)}U{f(uv)|uv∈E(G)，v∈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)，则称f为G的k-正常全染色．进一步，如果-f还满足(3)对任意uv∈E(G)，有C(u)≠C(v)，则称f为G的k-邻点可区别全染色(简记为k-AVDTC)．称min{k|G有k-邻点可区别全染色}为G的邻点可区别全色数，记为x<,at>(G)，其中C(u)称为点u在f下的色集合．
在第三章中，本文运用归纳法思想，得出了W<,m>ⅤP<,n>的邻点可区别全色数．
第四章在联图W<,m>ⅤP<,n>的基础上，仍然运用归纳法思想，得出了W<,m>ⅤC<,n>的邻点可区别全色数．主要结果如下：
定理对联图C<,n>ⅤK<,n>(n≥5)，有Xт(C<,n>ⅤK<,n>)=△+1．