路的半强积与强积的距离染色

doi:10.6040/j.issn.1671-9352.0.2024.094

摘要/Abstract

摘要： 图G的k-距离染色是指G中距离不超过k的顶点分配不同颜色的顶点染色,其中k∈N⁺。G的k-距离色数是指G的k-距离染色所用最少的颜色数,记为χ_k(G)。2个简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图,其中2个顶点(u,v)与(u',v')相邻当且仅当uu'∈E(G)且vv'∈E(H),或u=u'且vv'∈E(H)。2个简单图G与H的强积GH是具有顶点集V(G)×V(H)的简单图,其中2个顶点(u,v)与(u',v')相邻当且仅当uu'∈E(G)且vv'∈E(H),或u=u'且vv'∈E(H),或v=v'且uu'∈E(G)。对任意整数k≥2,得到了2个路的半强积与强积的k-距离色数。

关键词: 路, 半强积, 强积, 距离染色, 距离色数

Abstract: A k-distance coloring of a graph G is a vertex coloring of G such that no two vertices lying at distance less than or equal to k in G are assigned the same color. The k-distance chromatic number of G, denoted χ_k(G), is the minimum number of colors needed for a k-distance coloring of G. The semistrong product of simple graphs G and H is the graph G·H with vertex set V(G)×V(H), in which (u,v) is adjacent to (u',v') if and only if either uu'∈E(G) and vv'∈E(H) or u=u' and vv'∈E(H). The strong product of simple graphs G and H is the graph GH with vertex set V(G)×V(H), in which (u,v) is adjacent to (u',v') if and only if uu'∈E(G) and vv'∈E(H), or u=u' and vv'∈E(H), or v=v' and uu'∈E(G). In this paper, for any integer k≥2, the k-distance chromatic numbers of the semistrong product and the strong product of two paths are obtained.

Key words: path, semistrong product, strong product, distance coloring, distance chromatic number

中图分类号:

O157

田双亮,陈萍. 路的半强积与强积的距离染色[J]. 《山东大学学报(理学版)》, 2025, 60(12): 167-172.

TIAN Shuangliang, CHEN Ping. Distance colorings of the semistrong product and the strong product of paths[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(12): 167-172.

参考文献

[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. London: Macmillan Press Ltd, 1976.
[2] KRAMER F, KRAMER H. Un probleme de coloration des sommets dun graphe[J]. Comptes rendus de lAcademie bulgare des Sciences Paris A, 1969, 268:46-48.
[3] KRAMER F, KRAMER H. Ein Färbungsproblem der Knotenpunkte eines Graphen bezülich der Distanz p[J]. Revue Roumaine de Mathematiques Pures et Appliquees, 1969, 14(2):1031-1038.
[4] KRUMKE S O, MARATHE M V, RAVI S S. Models and approximation algorithms for channel assignment in radio networks[J]. Wireless Networks, 2001, 7:575-584.
[5] CHAITIN G J, AUSLANDER M A, CHANDRA A K, et al. Register allocation via coloring[J]. Computer Languages, 1981, 6:47-57.
[6] GEBREMEDHIN A H, MANNE F, POTHEN A. What color is your Jacobian? graph coloring for computing derivatives[J]. SIAM Review, 2005, 47:629-705.
[7] MIAO L Y, FAN Y Z. The distance coloring of graphs[J]. Acta Mathematica Sinica, English Series, 2014, 30(9):1579-1587.
[8] SHAHEEN R, KANAYA Z, JAKHLAB S. d-distance coloring of generalized petersen graphs P(n,k)[J]. Open Journal of Discrete Mathematics, 2017, 7:185-199.
[9] FERTIN G, GODARD E, RASPAUD A. Acyclic and k-distance coloring of the grid[J]. Information Processing Letters, 2003, 87(1):51-58.
[10] JACKO P, JENDROL S. Distance coloring of the hexagonal lattice[J]. Discussiones Mathematicae Graph Theory, 2005, 25:151-166.
[11] KIM B M, SONG B C, RHO Y. 2-distance colorings of some direct products of paths and cycles[J]. Discrete Mathematics, 2015, 338:1730-1739.
[12] JARADAT M M M. On the edge coloring of graph products[J]. International Journal of Mathematics and Mathematical Sciences, 2005, 16:2669-2676.

相关文章 15

[1]	周缪娟,黄韩亮,张纪平,李进金. 基于FT-粗糙集构建知识结构与寻找学习路径方法[J]. 《山东大学学报(理学版)》, 2025, 60(7): 116-130.
[2]	孙岩,张正,张夏然,刘耘麟,孙国华. 多重不确定环境下带有模糊软时间窗的多式联运路径优化与仿真[J]. 《山东大学学报(理学版)》, 2025, 60(6): 128-140.
[3]	刘乐民,逯峰,付志超,潘祖请,谢磊. 政府参与高速公路数字化转型的演化博弈[J]. 《山东大学学报(理学版)》, 2024, 59(9): 98-107.
[4]	王静红,吴芝冰,黄鹏,杨家腾,李笔. 基于元路径属性融合的异质网络表示学习[J]. 《山东大学学报(理学版)》, 2024, 59(3): 1-13.
[5]	朱莉,李鹏,王爱法. 单位区间图的半配对k-不相交路覆盖研究[J]. 《山东大学学报(理学版)》, 2024, 59(2): 80-90.
[6]	那宇嘉,谢珺,杨海洋,续欣莹. 融合上下文的知识图谱补全方法[J]. 《山东大学学报(理学版)》, 2023, 58(9): 71-80.
[7]	林宇静,李进金,陈惠琴. 形式背景下的多分知识结构与学习路径[J]. 《山东大学学报(理学版)》, 2023, 58(9): 114-126.
[8]	尹会玲,陈京荣,苏晓艳. 星图与二部图的某些乘积图上的k-路点覆盖[J]. 《山东大学学报(理学版)》, 2023, 58(6): 18-24, 39.
[9]	王忠林,刘树堂. 基于乘法器的混沌系统设计与实现[J]. 《山东大学学报(理学版)》, 2023, 58(3): 93-100.
[10]	何秋红,李进金,周银凤,吴靖. 面向属性概念在自适应技能测评中的实践应用[J]. 《山东大学学报(理学版)》, 2023, 58(12): 63-76.
[11]	仲诚诚,周恒,张梓童,张春雷. LAC-UNet: 基于胶囊表达局部-整体特征关系的语义分割模型[J]. 《山东大学学报(理学版)》, 2023, 58(11): 116-126.
[12]	卢鹏丽,栾睿,郭育红. 图的路(无符号)拉普拉斯谱半径及其能量[J]. 《山东大学学报(理学版)》, 2022, 57(7): 14-21.
[13]	王亮,景康康,彭佳慧,徐伟. 非光滑变换下随机碰撞系统的路径积分算法[J]. 《山东大学学报(理学版)》, 2022, 57(3): 68-77.
[14]	索孟鸽,陈京荣,张娟敏. 笛卡尔乘积图的k-路点覆盖[J]. 《山东大学学报(理学版)》, 2022, 57(12): 103-110.
[15]	邹难,谢磊,金宗凯,蔡兴茂,邵晨. 考虑承载能力的大型物流园区运输路径优化研究——以临沂市某物流园区为例Symbol`@@[J]. 《山东大学学报(理学版)》, 2021, 56(7): 11-20.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed