平面图的严格邻点可区别染色  

Strict neighbor-distinguishing edge coloring of planar graphs

作　　者：井普宁 王维凡[1] 王艺桥[2] 郑丽娜[1] Puning Jing;Weifan Wang;Yiqiao Wang;Lina Zheng

机构地区：[1]浙江师范大学数学科学学院,金华321004 [2]北京中医药大学管理学院,北京100029

出　　处：《中国科学：数学》2023年第3期523-542,共20页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:12031018,11771402,12071048和12161141006)资助项目。

摘　　要：图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.

关 键 词：严格邻点可区别边染色 局部严格邻点可区别边染色 平面图 围长 

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