圈与路的笛卡尔乘积图的多彩染色

On the r-hued Coloring of Cartesian Product of Cycle and Path

图的多彩染色问题是图论中的热点问题,它可应用于诸如电力网络的最优重新配置中多代理系统的通讯问题。图G的(k,r)-染色是图G的一个正常k-染色(k,r为正整数),并满足图G中的每一个顶点的邻点的颜色数至少为这个顶点的度d(v)和r的最小值。使得图G有(k,r)-染色的最小整数k称为图G的r-多彩色数,用χr(G)表示。研究了圈与路的笛卡尔乘积图Cm□Pn的r-多彩染色,得到了该类图的r-多彩染色数。

The r-hued coloring of graphs is a hot topic in graph theory,which can be applied to fields like the communication of multi-agent systems in the optimal reconfiguration of power networks.An(k,r)-coloring of G is a proper coloring with k colors such that for every vertex v with degree d(v)in G,the color number of the neighbors of v is at least min{d(v),r}.The smallest integer k such that G has an(k,r)-coloring is called the r-hued chromatic number and denoted by r(G).In this paper,we study the r-hued coloring of Cartesian product of cycle and path,and obtain its r-hued chromatic number.