您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

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

•   • 上一篇    下一篇

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

雷飞1(),文飞1,*(),李泽鹏2,李沐春1   

  1. 1. 兰州交通大学应用数学研究所, 甘肃 兰州 730070
    2. 兰州大学信息科学与工程学院, 甘肃 兰州 730000
  • 收稿日期:2023-01-10 出版日期:2024-10-20 发布日期:2024-10-10
  • 通讯作者: 文飞 E-mail:leifei1997math@163.com;wenfei@lzjtu.edu.cn
  • 作者简介:雷飞(1997—), 女, 硕士研究生, 研究方向为图论及其应用. E-mail: leifei1997math@163.com
  • 基金资助:
    国家自然科学基金资助项目(11961041);国家自然科学基金资助项目(61802158);甘肃省自然科学基金资助项目(21JR11RA065)

Vertex reducible edge coloring of the Lexicographic product of graphs

Fei LEI1(),Fei WEN1,*(),Zepeng LI2,Muchun LI1   

  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
  • Received:2023-01-10 Online:2024-10-20 Published:2024-10-10
  • Contact: Fei WEN E-mail:leifei1997math@163.com;wenfei@lzjtu.edu.cn

RichHTML

2

PDF (PC)

166

摘要：

设$f: E(G) \rightarrow\{1, 2, \cdots, 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}\left[\overline{K_{2 m}}\right], K_{n}[H]$和Pn[H]的点可约边色数。

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

Abstract:

Let $f: E(G) \rightarrow\{1, 2, \cdots, 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}\left[\overline{K_{2 m}}\right], K_{n}[H]$ and Pn[H] are obtained.

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

中图分类号: 

  • O157.5

图1

图Pn[Pm]的拆分方式1"

图2

图Pn[Pm]的拆分方式2"

图3

图$P_{n}[H]$的点可约边染色"

1 ZHANGZ F,LIUL Z,WANGJ F.Adjacent strong edge coloring of graphs[J].Applied Mathematics Letters,2002,15(5):623-626.
doi: 10.1016/S0893-9659(02)80015-5
2 李沐春,文飞,张荔.图K2n+1\E(K2, m)的点可区别全染色[J].南开大学学报(自然科学版),2012,45(6):59-65.
LIMuchun,WENFei,ZHANGLi.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.
LIZepeng,GENGPeilun,CHENGXiang'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.
JIAXiuqing,LIMuchun.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 WALDEMARS,IWONAW,ANDRZEJW.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.
doi: 10.1016/j.disc.2007.08.078
8 TIANS L,WANGQ.Adjacent vertex distinguishing edge-colorings and total-colorings of the lexicographic product of graphs[J].Discrete Mathematics,2015,185,220-226.
doi: 10.1016/j.dam.2014.11.028
9 田双亮,杨环,索郎王青,等.路的字典积的邻和可区别边染色[J].运筹学学报,2020,24(1):140-146.
TIANShuangliang,YANGHuan,SUOLANGWangqing,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.
LIJingwen,KANGYumei,ZHANGShucheng,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.
LUORong,LIJingwen,ZHANGShucheng,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 BONDYJ A,MURTYU S R.Graph theory with applications[M].London:Macmillan Press Ltd.,1976.
[1] 田双亮. 若干图的广义字典积的点可区别边染色[J]. 山东大学学报（理学版）, 2014, 49(06): 31-34.
[2] 田双亮. 若干字典积图的Mycielski图的点可区别边染色[J]. J4, 2012, 47(8): 7-10.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 刘洪华 . 色散方程的交替分组迭代方法[J]. J4, 2007, 42(1): 19 -23 .
[2] 刘昆仑. 变结构pair copula模型在金融危机传染分析中的应用[J]. 山东大学学报（理学版）, 2016, 51(6): 104 -110 .
[3] 郭乔进,丁轶,李宁. 一种基于上下文信息的乳腺肿块ROI检测方法[J]. J4, 2010, 45(7): 70 -75 .
[4] 付海艳,卢昌荆,史开泉 . (F,F-)-规律推理与规律挖掘[J]. J4, 2007, 42(7): 54 -57 .
[5] 郭文鹃,杨公平*,董晋利. 指纹图像分割方法综述[J]. J4, 2010, 45(7): 94 -101 .
[6] 张雯,张化祥*,李明方,计华. 决策树构建方法:向前两步优于一步[J]. J4, 2010, 45(7): 114 -118 .
[7] 宋 颖,张兴芳,王庆平 . 参数Kleene系统的α-反向三Ⅰ支持算法[J]. J4, 2007, 42(7): 45 -48 .
[8] 刘战杰1,马儒宁1,邹国平1,钟宝江2,丁军娣3. 一种新的基于区域生长的彩色图像分割算法[J]. J4, 2010, 45(7): 76 -80 .
[9] . pLaplacian边值问题的多重正解[J]. J4, 2009, 44(7): 79 -82 .
[10] . 中国电力市场的多寡头动态离散模型[J]. J4, 2009, 44(5): 91 -96 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发