JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2024, Vol. 59 ›› Issue (10): 107-114.doi: 10.6040/j.issn.1671-9352.0.2023.032

Previous Articles    

Vertex reducible edge coloring of the Lexicographic product of graphs

LEI Fei1, WEN Fei1*, LI Zepeng2, LI Muchun1   

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

PDF (PC)

17

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 Kn［K2m^-］, Kn［H］ and Pn［H］ are obtained.

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

CLC Number: 

  • O157.5
[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.
[1] TIAN Shuang-liang. Vertex-distinguishing edge coloring of the generalized lexicographic product of some graphs#br# [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(06): 31-34.
[2] WANG Dong-yan, LI Shenggang*, YANG Wen-hua. The product operations and related decompostions of fuzzy graphs [J]. J4, 2013, 48(6): 104-110.
[3] TIAN Shuang-liang. Vertex-distinguishing edge colorings of the Mycielski′s graphs of  some lexicographic product graphs [J]. J4, 2012, 47(8): 7-10.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd