在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2023, Vol. 40 ›› Issue (6): 979-990.doi: 10.3969/j.issn.1005-3085.2023.06.009

• • 上一篇    下一篇

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

张春梅,  史雅馨,  杜伊诺   

  1. 新疆大学数学与系统科学学院，乌鲁木齐 830017
  • 收稿日期:2023-08-18 接受日期:2023-09-28 出版日期:2023-12-15 发布日期:2024-02-15

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

ZHANG Chunmei,  SHI Yaxin,  DU Yinuo   

  1. School of Mathematics and System Sciences, Xinjiang University, Urumqi 830017
  • Received:2023-08-18 Accepted:2023-09-28 Online:2023-12-15 Published:2024-02-15

摘要：

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

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

Abstract:

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 by $\chi_{r}(G)$. In this paper, we study the $r$-hued coloring of Cartesian product of cycle and path, and obtain its $r$-hued chromatic number.

Key words: $(k,r)$-coloring, $r$-hued coloring number, Cartesian product, cycle, path

中图分类号: