子立方图的D(2)-点和可区别边染色

强会英; 何静

兰州交通大学学报 ›› 2026, Vol. 45 ›› Issue (5) : 42 -48.

子立方图的D(2)-点和可区别边染色

强会英, 何静

作者信息 +

Author information +

文章历史 +

摘要

子立方图是指最大度不超过3的简单连通图。正常子立方图是最小度至少为2的立方图，即图中任意顶点的度数在2与3之间。图的D(2)-点和可区别边染色是指图的一个正常边染色，满足图中任意两个距离不超过2的顶点u、 v，其关联边所染的颜色数之和互不相同。本文通过分析子立方图的结构特点，利用反证法和极小反例原理假设子立方图不存在某一最小性质的反例，又有矛盾证明极小反例存在，最后又由整个断言存在矛盾进而证明定理成立，组合零点定理通过代数工具分析结构中元素数量关系，多维度揭示了子立方图的结构特点，讨论了子立方图的D(2)-点和可区别边染色问题，得到了其D(2)-点和可区别边色数不超过12，为图论中图的染色理论研究提供新的理论成果与实践参考。