3≤Δ≤4的图的D(2)-点和可区别全染色

摘要

[目的]探究最大度满足3≤Δ≤4的简单连通图G的D(2)-点和可区别全染色特性,明确其D(2)-点和可区别全色数,进而拓展该染色问题在平面图中的研究结论,为图论中相关染色理论的完善提供支撑.[方法]采用组合零点定理与权转移方法相结合的研究手段.通过组合零点定理构建染色存在性的理论基础,借助权转移方法分析图中顶点与边的权值分配关系,验证染色方案的合理性与可行性.[结果]成功确定了3≤Δ≤4的简单连通图G的D(2)-点和可区别全色数的值;进一步将该结论推广至平面图范畴,证明了满足3≤Δ≤4的平面图同样具备相应的D(2)-点和可区别全染色性质,且其点和可区别全色数与简单连通图保持一致.[结论]组合零点定理与权转移方法可有效解决3≤Δ≤4图类的D(2)-点和可区别全染色问题,所得色数结论对简单连通图及平面图均适用,为后续研究图的最大度在其他范围内的此类色数问题提供了可借鉴的方法与理论依据.

关键词

D(2)-点和可区别全染色 / 组合零点定理 / 权转移方法