论文部分内容阅读
图的顶点正常着色是对顶点分配颜色使得相邻顶点的颜色不同。图的顶点自由着色是对顶点分配颜色而允许相邻顶点的颜色相同。图的边正常着色以及边自由着色的定义是类似的。图的全着色是对顶点和边分配颜色使得相邻顶点、相邻边、顶点和关联边分配不同的颜色。图的自由全着色是对顶点和边分配颜色而没有其他条件限制。设c是图G的一个着色，如果这个着色c导出了顶点的一种标号使得图G任何相邻顶点可以通过这个标号进行区分，那么就称c是G的一个邻点可区分着色。这篇论文研究了三种类型的关于图的邻点可区分着色概念:图的多重集着色、图的邻点可区分全着色、图的邻域之和邻点可区分点着色。主要内容概括如下: (1)图的多重集着色。图G的一个顶点自由κ-着色如果使得图G任何相邻顶点的多重集不同，那么就称该着色是图G的一个多重集κ-着色，这里每个顶点υ的多重集是υ的所有邻点颜色的多重集。使得图G存在多重集κ-着色的最小κ值就称为图G的多重集色数。本论文解决了Chartrand提出的关于多重集着色圈的幂次方图的一个猜想。另外，本文提出了广义Corona图概念。因为这个概念的提出，现有文献中关于多重集着色的结果都得到了推广。 (2)图的邻点可区分全着色。图G的一个全κ-着色如果使得图G任何相邻顶点的颜色集不同，那么就称该着色是图G的一个邻点可区分全κ-着色，这里每个顶点υ的颜色集是由出现在υ点及其所有关联边上颜色构成的集合。使得图G存在邻点可区分全κ-着色的最小κ值就称为图G的邻点可区分全色数。Hulgan在其博士论文中介绍了一类三正则图:snares图，并得到了snares图的邻点可区分全色数的部分结果。本文完全确定了snares图的邻点可区分全色数。本文还考虑了另外两类三正则图的邻点可区分全色数:一类三正则Hamilton图和广义Petersen图。本文得到的这些结果对进一步研究Hulgan提出的关于6是否是任意最大度数为三的图的邻点可区分全色数的紧的上界这个问题提供了一个鼓舞人心的信息。最后，本文研究了一类连接图的邻点可区分全色数问题，并得到了相关结果。 (3)图的邻域之和邻点可区分点着色。图G的一个顶点正常κ-着色如果使得图G的任何相邻顶点的邻域之和不同，那么就称该着色是图G的一个邻域之和邻点可区分顶点κ-着色，这里每个顶点υ的邻域之和是指υ的所有邻点颜色之和。使得图G存在邻域之和邻点可区分顶点κ-着色的最小κ值就称为图G的邻域之和邻点可区分点色数。本文确定了路、圈、圈的平方图、圈的三次方图和完全多部图等图的邻域之和邻点可区分点色数。同时，得到了树、单圈图和三正则图的紧的邻域之和邻点可区分点色数上界。根据这些基本结果得到了关于任何图G的邻域之和邻点可区分点色数上界的一个猜想。