图的字典积的点可约边染色

doi:10.6040/j.issn.1671-9352.0.2023.032

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (10): 107-114.doi: 10.6040/j.issn.1671-9352.0.2023.032

• • 上一篇

图的字典积的点可约边染色

雷飞¹,文飞^1*,李泽鹏²,李沐春¹

1.兰州交通大学应用数学研究所, 甘肃兰州 730070;2.兰州大学信息科学与工程学院, 甘肃兰州 730000

发布日期:2024-10-10
通讯作者: 文飞(1984— ), 男,教授,博士,研究方向为图染色、图谱理论. E-mail:wenfei@lzjtu.edu.cn
基金资助:
国家自然科学基金资助项目(11961041,61802158);甘肃省自然科学基金资助项目(21JR11RA065)

Vertex reducible edge coloring of the Lexicographic product of graphs

LEI Fei¹, WEN Fei^1*, LI Zepeng², LI Muchun¹

1. Institute of Applied Mathematics, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China;
2. School of Information Science and Engineering, Lanzhou University, Lanzhou 730000, Gansu, China

Published:2024-10-10

摘要/Abstract

摘要： 设f:E(G)→{1,2,…,k}是图G的一个(非正常)边染色,其中1≤k≤Δ,若对任意2个顶点u,v∈V(G)且d(u)=d(v)时,满足C(u)=C(v),则称f是图G的一个点可约k-边染色,其中C(u)表示点u关联边上分配的颜色组成的色集合。将最大的正整数k称为图G的点可约边色数。根据字典积图的结构特点,运用组合分析法给出了简单图G和H的字典积G［H］的点可约边色数的一个下界。作为应用,得到了图K_n［K_2m^-］,K_n［H］和P_n［H］的点可约边色数。

关键词: 字典积, 点可约边染色, 点可约边色数

Abstract: Let f:E(G)→{1,2,…,k} be a non-proper k-edge coloring of G, and 1≤k≤Δ. If for any two adjacent vertices u,v∈V(G) with d(u)=d(v) satisfy C(u)=C(v), f is called a k-vertex-reducible edge coloring, where C(u) denotes the set of colors of edges incident with u. The maximum positive integer k is called vertex-reducible edge chromatic number of G. According to the characters of the lexicographic product graphs, we apply combinatorial analysis to give a lower bound of the vertex reducible edge chromatic number of the lexicographic product G［H］ for simple graphs G and H. As applications, the vertex-reducible edge chromatic numbers of K_n［K2m^-］, K_n［H］ and P_n［H］ are obtained.

Key words: lexicographic product, vertex reducible edge coloring, vertex reducible edge chromatic number

中图分类号:

O157.5

雷飞,文飞,李泽鹏,李沐春. 图的字典积的点可约边染色[J]. 《山东大学学报(理学版)》, 2024, 59(10): 107-114.

LEI Fei, WEN Fei, LI Zepeng, LI Muchun. Vertex reducible edge coloring of the Lexicographic product of graphs[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(10): 107-114.

参考文献

[1] ZHANG Z F, LIU L Z, WANG J F. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15(5):623-626.
[2] 李沐春,文飞,张荔. 图K2n+1\E(K2,m)的点可区别全染色[J]. 南开大学学报(自然科学版), 2012, 45(6):59-65. LI Muchun, WEN Fei, ZHANG Li. Vertex-distinguishing total coloring of K2n+1\E(K2,m)[J]. Journal of Nankai University(Natural Science Edition), 2012, 45(6):59-65.
[3] 李泽鹏,耿培伦,陈祥恩. 树的D(r)-点可区别边染色[J]. 广州大学学报(自然科学版), 2020, 19(1):1-7. LI Zepeng, GENG Peilun, CHENG Xiangen. The D(r)-vertex-distinguishing edge coloring of trees[J]. Journal of Guangzhou University(Natural Science Edition), 2020, 19(1):1-7.
[4] 贾秀卿,李沐春. 单圈图的D(2)-点可区别边染色[J]. 吉林大学学报(理学版), 2021, 59(4):807-815. JIA Xiuqing, LI Muchun. D(2)-vertex-distinguishing edge coloring of unicyclic graphs[J]. Journal of Jilin University(Science Edition), 2021, 59(4):807-815.
[5] LI J W, ZHANG Z F, ZHU E Q, et al. Adjacent vertex reducible edge-total coloring of graphs[C] //2009 2nd International Conference on Biomedical Engineering and Informatics. New York: IEEE Press, 2009:1-3.
[6] 朱恩强. 若干图类的新染色问题[D]. 兰州:兰州交通大学, 2010. ZHU Enqiang. The new coloring problems of some graphs[D]. Lanzhou: Lanzhou Jiaotong University, 2010.
[7] WALDEMAR S, IWONA W, ANDRZEJ W. On the existence and on the number of(k,l)-kernels in the lexicographic product of graphs[J]. Discrete Mathematics, 2008, 308(20):4616-4624.
[8] TIAN S L, WANG Q. Adjacent vertex distinguishing edge-colorings and total-colorings of the lexicographic product of graphs[J]. Discrete Mathematics, 2015, 185:220-226.
[9] 田双亮,杨环,索郎王青,等. 路的字典积的邻和可区别边染色[J]. 运筹学学报, 2020, 24(1):140-146. TIAN Shuangliang, YANG Huan, SUOLANG Wangqing, et al. Neighbor sum distinguishing edge coloring of the lexicographic product of paths[J]. Operations Research Transactions, 2020, 24(1):140-146.
[10] 李敬文,康玉梅,张树成,等. 图的点和可约边染色[J]. 武汉大学学报(理学版), 2022, 68(5):487-495. LI Jingwen, KANG Yumei, ZHANG Shucheng, et al. Vertex sum reducible edge coloring of graphs[J]. Journal of Wuhan University(Science Edition), 2022, 68(5):487-495.
[11] 罗榕,李敬文,张树成,等. 若干联图的邻点和可约边染色[J]. 华中师范大学学报(自然科学版), 2023, 57(2):201-207. LUO Rong, LI Jingwen, ZHANG Shucheng, et al. Adjacent points sum reducible edge coloring of some joint graphs[J]. Journal of Central China Normal University(Natural Science Edition), 2023, 57(2):201-207.
[12] BONDY J A, MURTY U S R. Graph theory with applications[M]. London: Macmillan Press Ltd., 1976.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

图的字典积的点可约边染色

Vertex reducible edge coloring of the Lexicographic product of graphs

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

多维度评价

本文评价

推荐阅读 0

[1]	田双亮. 若干图的广义字典积的点可区别边染色[J]. 山东大学学报（理学版）, 2014, 49(06): 31-34.
[2]	田双亮. 若干字典积图的Mycielski图的点可区别边染色[J]. J4, 2012, 47(8): 7-10.