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

Vertex reducible edge coloring of the Lexicographic product of graphs

作　　者：雷飞 文飞[1] 李泽鹏 李沐春[1] LEI Fei;WEN Fei;LI Zepeng;LI Muchun(Institute of Applied Mathematics,Lanzhou Jiaotong University,Lanzhou 730070,Gansu,China;School of Information Science and Engineering,Lanzhou University,Lanzhou 730000,Gansu,China)

机构地区：[1]兰州交通大学应用数学研究所,甘肃兰州730070 [2]兰州大学信息科学与工程学院,甘肃兰州730000

出　　处：《山东大学学报（理学版）》2024年第10期107-114,共8页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金资助项目(11961041,61802158);甘肃省自然科学基金资助项目(21JR11RA065)。

摘　　要：设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]的点可约边色数。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)[K_(2m)],K_(n)[H]and P_(n)[H]are obtained.

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

分 类 号：O157.5[理学—数学]