乘积图与正则图的满着色

摘要

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