笛卡尔积图的r-hued染色  

On r-hued coloring of Cartesian product graphs

作　　者：杨晓梅[1] 唐梦 刘博予 YANG Xiao-mei;TANG Meng;LIU Bo-yu(College of Mathematics and System Sciences,Xinjiang University,Urumqi 830017,China)

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

出　　处：《兰州理工大学学报》2024年第6期167-172,共6页Journal of Lanzhou University of Technology

基　　金：国家自然科学基金(11961067)。

摘　　要：图G的r-hued色数χ_(r)(G)是图G的所有(k,r)-染色中最小的k.图G和图H的笛卡尔积图G□H,即顶点集为V(G)×V(H)的图,若(u,v)与(x,y)相邻当且仅当u=x,vy∈E(H)或v=y,ux∈E(G).讨论圈的平方图与路的笛卡尔积图C_(m)^(2)□P_(n)的r-hued染色问题,运用构造法,通过图C_(m)^(2)□P_(n)的结构关系确定了r=2及r=3时C_(m)^(2)□P_(n)的r-hued色数.The r-hued chromatic number of a graph G is the minimum number k of all(k,r)-colorings,denoted byχr(G).The Cartesian product of G and H is denoted by G□H with vertex set V(G)×V(H),where two vertices(u,v)and(x,y)are adjacent if and only if either u=x and vy∈E(H)or v=y and ux∈E(G).The r-hued chromatic number of the Cartesian product graph C_(m)^(2)□P_(n)is discussed.By applying a constructive method and considering the structural relationships of C_(m)^(2)□P_(n),the r-hued chromatic number of C_(m)^(2)□P_(n)is obtained for r=2,3.

关 键 词：路 圈的平方图 笛卡尔积图 r-hued染色 

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