限制最大平均度下图的邻点全和可区别全染色

摘要

图G的邻点全和可区别全染色是一个满足任意两个相邻顶点的全和不同的正常全染色，其中顶点的全和是该点及其关联元素所染的颜色之和.将所用的最少颜色数称为G的邻点全和可区别全色数，简记为ftndi_Σ（G）.设mad（G）和Δ（G）分别表示图G的最大平均度和最大度，运用组合零点定理与权转移法得到：（i）若Δ（G）=3且■，则ftndi_Σ（G）≤6;（ii）若Δ（G）=4且■，则ftndi_Σ（G）≤8;（iii）若Δ（G）≥5且■，则ftndi_Σ（G）≤max{9，Δ（G）+2}.从而推知，当图G满足Δ（G）≥7且■时，邻点全和可区别全染色猜想（崔福祥等，2023）是成立的.

关键词

正常全染色 / 邻点全和可区别全染色 / 最大平均度 / 组合零点定理