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

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

作　　者：张春梅[1] 史雅馨 杜伊诺 ZHANG Chunmei;SHI Yaxin;DU Yinuo(School of Mathematics and System Sciences,Xinjiang University,Urumqi 830017)

机构地区：[1]新疆大学数学与系统科学学院,乌鲁木齐830017

出　　处：《工程数学学报》2023年第6期979-990,共12页Chinese Journal of Engineering Mathematics

摘　　要：图的多彩染色问题是图论中的热点问题,它可应用于诸如电力网络的最优重新配置中多代理系统的通讯问题。图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 byr(G).In this paper,we study the r-hued coloring of Cartesian product of cycle and path,and obtain its r-hued chromatic number.

关 键 词：(k r)-染色 r-多彩染色数 笛卡尔乘积图 圈 路 

分 类 号：O157.5[理学—数学]