图的字典积的点可约边染色
Vertex reducible edge coloring of the Lexicographic product of graphs
雷飞 1文飞 1李泽鹏 2李沐春1
作者信息
- 1. 兰州交通大学应用数学研究所,甘肃兰州 730070
- 2. 兰州大学信息科学与工程学院,甘肃兰州 730000
- 折叠
摘要
设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]的点可约边色数的一个下界.作为应用,得到了图Kn[(K2m)],Kn[H]和Pn[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 chro-matic numbers of Kn[K2m],Kn[H]and Pn[H]are obtained.
关键词
字典积/点可约边染色/点可约边色数Key words
lexicographic product/vertex reducible edge coloring/vertex reducible edge chromatic number引用本文复制引用
基金项目
国家自然科学基金资助项目(11961041)
国家自然科学基金资助项目(61802158)
甘肃省自然科学基金资助项目(21JR11RA065)
出版年
2024
NETL
NSTL
万方数据