笛卡尔积图的r-hued染色

兰州理工大学学报 ›› 2024, Vol. 50 ›› Issue (6): 167-172.

• 数理科学 • 上一篇

笛卡尔积图的r-hued染色

杨晓梅^*, 唐梦, 刘博予

新疆大学数学与系统科学学院, 新疆乌鲁木齐 830017

收稿日期:2023-03-14 出版日期:2024-12-28 发布日期:2025-01-13
通讯作者: 杨晓梅(1980-),女,新疆乌鲁木齐人,博士,讲师.Email:yxm_xju@126.com
基金资助:
国家自然科学基金(11961067)

On r-hued coloring of Cartesian product graphs

YANG Xiao-mei, TANG Meng, LIU Bo-yu

College of Mathematics and System Sciences, Xinjiang University, Urumqi 830017, China

Received:2023-03-14 Online:2024-12-28 Published:2025-01-13

摘要/Abstract

摘要： 图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□P_n的r-hued染色问题,运用构造法,通过图C²_m□P_n的结构关系确定了r=2及r=3时C²_m□P_n的r-hued 色数.

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

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

中图分类号:

O157.5

杨晓梅, 唐梦, 刘博予. 笛卡尔积图的r-hued染色[J]. 兰州理工大学学报, 2024, 50(6): 167-172.

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.

参考文献

[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.

笛卡尔积图的r-hued染色

On r-hued coloring of Cartesian product graphs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张文旭, 王晓晴, 陈辉, 赵永红. 基于智能优化决策的目标跟踪传感器路径规划[J]. 兰州理工大学学报, 2024, 50(6): 92-98.
[2]	田振际, 豆舒平. 3 di-sk树的计数[J]. 兰州理工大学学报, 2024, 50(6): 144-149.
[3]	张红英, 李旭升, 袁华智, 高虹. 深基坑开挖对临近高速公路影响及支护系统受力与变形研究[J]. 兰州理工大学学报, 2024, 50(3): 123-129.
[4]	杨胜良, 王楠. 部分Motzkin路的计数[J]. 兰州理工大学学报, 2024, 50(3): 137-142.
[5]	王亚芹. 限定高度的Dyck路的计数[J]. 兰州理工大学学报, 2024, 50(1): 168-172.
[6]	金明亮, 韦正鹏. 湿陷性黄土地区水泥改良土路床的现场试验研究[J]. 兰州理工大学学报, 2023, 49(3): 135-139.
[7]	王勋, 王斐儒, 商国旭. 基于多链路无线传感器网络的级联模型及算法[J]. 兰州理工大学学报, 2023, 49(2): 96-102.
[8]	杨胜良, 姜美杨. 混合d-元树上的模式避免问题[J]. 兰州理工大学学报, 2023, 49(2): 144-150.
[9]	颜闽秀, 谢俊红, 张帅. 具有多稳态和可调数目吸引子共存的混沌系统[J]. 兰州理工大学学报, 2022, 48(6): 88-95.
[10]	李萍, 毛昱, 王盟, 丁樊, 瞿晓成. 冻融循环条件下外掺剂对沥青混合料水稳定性的影响[J]. 兰州理工大学学报, 2022, 48(1): 107-113.
[11]	杨胜良,任凤云. 广义Jacobsthal数及其组合意义[J]. 兰州理工大学学报, 2021, 47(6): 151-155.
[12]	叶帅华, 樊黎明, 时轶磊. 考虑砂岩残余强度的二元结构深挖路堑边坡稳定性分析[J]. 兰州理工大学学报, 2021, 47(5): 106-114.
[13]	于正永, 朱建平, 唐万春. 一种宽带带通三维频率选择表面设计及分析[J]. 兰州理工大学学报, 2021, 47(3): 86-90.
[14]	王惠琴, 马玉昆, 蔡红亮, 张悦, 曹明华. 无线激光数据通信系统收发电路的设计与实现[J]. 兰州理工大学学报, 2021, 47(3): 91-96.
[15]	高嫄嫄, 王维玉, 赵庆新, 焦彦鹏. 基于解析方法的开裂水泥混凝土路面动力响应[J]. 兰州理工大学学报, 2021, 47(2): 144-150.