有关满着色的一些结果

Some result on fall coloring

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

A coloring of a graph G = （ V, E） is a partition Π = { V1, V2,…, Vk } of the vertices of G into independent sets or color classes.A vertex v∈Vi is called colorful if it is adjacent to at least one vertex in every color class Vj, i ≠j. A fall coloring is a coloring in which every vertex is colorful. If a graph has a fall coloring, we define the fall chromatic number（fall achromatic number）of G,denoted χf（ G）（ψf（ G））to equal the minimum （maximum） munbers of colorsused in a fall coloring of G, respectively. In this paper we get some new result of fall coloring on perfect graphs.