On r-hued coloring of Cartesian product graphs

Abstract

Abstract: 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□P_n is discussed. By applying a constructive method and considering the structural relationships of C²_m□P_n, the r-hued chromatic number of C²_m□P_n is obtained for r=2,3.

Key words: path, square graph of cycles, Cartesian product graph, r-hued coloring

CLC Number:

O157.5

YANG Xiao-mei, TANG Meng, LIU Bo-yu. On r-hued coloring of Cartesian product graphs[J]. Journal of Lanzhou University of Technology, 2024, 50(6): 167-172.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://journal.lut.edu.cn/EN/

https://journal.lut.edu.cn/EN/Y2024/V50/I6/167

References

[1] KONDO H,SUZUKI Y,IWAMOTO S.Intelligent reconfiguration of smart distribution network using multi-agent technology[C].Calgary:IEEE Power & Energy Society General Meeting,2009:2187-2192.
[2] AGUSTIN I H,DAFIK,HARSYA A Y.On r-dynamic coloring of some graph operations[J].Indonesian Journal of Combinatorics,2016,1(1):22-30.
[3] DONG W,XU B.2-Distance coloring of planar graphs with girth 5[J].Journal of Combinatorial Optimization,2017,34(4):1302-1322.
[4] BU Y H,WANG X F.r-hued coloring of planar graphs without short cycles[J].Discrete Mathematics Algorithms Applications,2020,12(3):2050034.
[5] VIZING V G.Vertex colorings with given colors (in Russian)[J].Metody Diskret Analiz,2976,29:3-10.
[6] CHEN Y,FAN S H,LAI H J,et al.On dynamic coloring for planar graphs and graphs of higher genus[J].Discrete Applied Mathematics,2012,160(7/8):1064-1071.
[7] 张明,贾泽乐,李沐春.几种笛卡尔积图的集合边染色[J].兰州交通大学学报,2021,40(4):134-139.
[8] BONDY J A,MURTY U S R.Graph theory[M].New York:Springer,2008.
[9] BONDY J A,MURTY U S R.Graph theory with applications[M].London:The Macmillan Press Ltd,1976.
[10] AKBARI S,GHANBARI M,JAHANBEKAM S.On the dynamic coloring of cartesian product graphs[J].Ars Combinatoria,2014,114(51):161-168.
[11] JAHANBEKAM S,KIM J,WEST D.On r-dynamic coloring of graphs[J].Discrete Applied Mathematics,2016,160(14):65-72.
[12] KANG R,MÜLLER T,WEST D.On r-dynamic coloring of grids[J].Discrete Applied Mathematics,2015,186(14):286-290.
[13] SUIL O.Matchings,connectivity,and eigenvalues in regular graphs[D].Urbana-Champaign:University of Illinois-Urbana-Champaign,2011.
[14] SHAO R,ZUO L.r-hued coloring of cartesian product of path with its square[J].Advances in Mathematics,2019,48(1):21-28.
[15] KALIRAJ K,NARESH K,VERNOLD V.On dynamic colouring of cartesian product of complete graph with some graphs[J].Journal of Taibah University for Science,2020,14(1):168-171.