论文部分内容阅读
图G=（V，E）的一个正常k-着色实际上是将G的顶点划分为独立集，记为Π={V1，V2，…，Vk}．其中Vi，i=1，2，…，k，也称色类．对于任一色类Vi中的点v，如果它与其余色类中至少一个点相邻，则v被称为是满色的．如果在G的一个正常k-着色中，所有点都是满色的，则称这样的着色是满着色．如果一个图存在满着色，定义图的满着色数为使得图存在满着色的最小颜色数，记为χf（G）．另外，记ψ（G）为使图存在满着色的最大颜色数．本文主要研究了有关满着色的一些性质，并给出一个满着色与完美图之间的结论．