乘积图与正则图的满着色

Fall Colorings on Cartesian Products and Regular Graphs

图G=(V,E)的一个正常着色就是将G的顶点划分为独立集,或称之为色类,记为 ={V1,V2,…,Vk}.对于任一色类Vi中的点v,如果它与其余色类中至少一个点相邻,则v被称为是满色的.如果在一个正常着色中,所有点都是满色的,则称这样的着色是满着色.如果一个图存在满着色,定义图的满着色数为使得图存在满着色的最小颜色数,记为χf(G).另外,记ψf(G)为使图存在满着色的最大颜色数.在这篇文章中,我们研究了一些乘积图的满着色,得出一些关于正则图的满着色的结果.

A coloring of a graph G=(V,E) is a partition ={V_1,V_2,…,V_k} of the vertices of G into independent sets or color classer. A vertex v∈V_i is called colorful if it is adjacent to at least one vertex in every color class V_j,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 unmber (fall achromatic number) of G, denoted χ_f(G)(ψ_f(G)) to equal the minimum (maximum) numbers of colors used in a fall coloring of G, respectively. In this paper we study fall coloring of cartesian products and get some results on the fall colorings of regular graphs.