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

李志军, 文飞, 岳忠政

doi:10.13471/j.cnki.acta.snus.ZR20240354

中山大学学报（自然科学版中英文） ›› 2026, Vol. 65 ›› Issue (1) : 135 -143. DOI: 10.13471/j.cnki.acta.snus.ZR20240354

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

李志军, 文飞, 岳忠政

作者信息 +

Author information +

文章历史 +

摘要

图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）是成立的.