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

作者：张春梅; 史雅馨; 杜伊诺

来源：工程数学学报, 2023, 40(06): 979-990.

• (k, r)-染色
• r-多彩染色数
• 笛卡尔乘积图
• 圈
• 路

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