|
|||||
|
|
| 平面图的严格邻点可区别染色 | |
| 作者姓名： | 井普宁 王维凡 王艺桥 郑丽娜 |
| 作者单位： | 1. 浙江师范大学数学科学学院;2. 北京中医药大学管理学院 |
| 基金项目： | 国家自然科学基金(批准号: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的情形. |
| 关 键 词： | 严格邻点可区别边染色 局部严格邻点可区别边染色 平面图 围长 |