摘要
图G的严格邻点可区别边染色是一个正常边染色,使得每对相邻顶点所关联的边的颜色集合互不包含.G的严格邻点可区别边色数χ’snd(G)是使G有一个严格邻点可区别k-边染色的最小整数k.本领域存在一个重要猜想:除去一个特殊图HΔ外,每个没有叶子的简单图G都满足χ’snd(G)≤2Δ.当前最好的已知上界是χ’snd(G)≤3Δ-1.一个自然而有趣的问题是,哪类没有叶子的图满足χ’snd(G)≤Δ+C,其中C是一个不依赖于最大度Δ的常数?本文部分地回答了这个问题,即证明了对围长至少为5的平面图G,有χ’snd(G)≤Δ+25.这里围长大于等于5的条件不能被减弱到小于等于4的情形.
A proper edge coloring of a graph G is strict neighbor-distinguishing if for any two adjacent vertices u and v,the set of colors used on the edges incident to u and the set of colors used on the edges incident to v do not include each other.The strict neighbor-distinguishing index of G is the minimum numberχsnd’(G)of colors in a strict neighbor-distinguishing edge coloring of G.It is conjectured that every simple graph G without leaves satisfiesχsnd’(G)≤2Δexcept a special graph HΔ.The currently best-known upper bound isχsnd’(G)≤3Δ-1.An interesting question is:Which graphs G without leaves satisfyχsnd’(G)≤Δ+C,where C is a constant?This paper partially answers this question,i.e.,it is proved that if G is a planar graph with a girth of at least five,thenχsnd’(G)≤Δ+25.
作者
井普宁
王维凡
王艺桥
郑丽娜
Puning Jing;Weifan Wang;Yiqiao Wang;Lina Zheng
出处
《中国科学：数学》
CSCD
北大核心
2023年第3期523-542,共20页
Scientia Sinica：Mathematica
基金
国家自然科学基金(批准号:12031018,11771402,12071048和12161141006)资助项目。
关键词
严格邻点可区别边染色
局部严格邻点可区别边染色
平面图
围长
strict neighbor-distinguishing edge coloring
local strict neighbor-distinguishing edge coloring
planar graph
girth
