双圈图的邻点全和可区别全染色

李志军; 文飞; 杨随义

doi:10.19603/j.cnki.1000-1190.2025.04.008

华中师范大学学报（自然科学版） ›› 2025, Vol. 59 ›› Issue (04) : 568 -576. DOI: 10.19603/j.cnki.1000-1190.2025.04.008

双圈图的邻点全和可区别全染色

李志军, 文飞, 杨随义

作者信息 +

Author information +

文章历史 +

PDF

摘要

设f是图G的一个正常k-全染色.令?（v）=f（v）+∑_v∈ef（e）+∑_u∈N（v）f（u）,其中N（v）={u∈V（G）|uv∈E（G）}.对任意的uv∈E（G）,若?（u）≠?（v）,则称f是图G的一个邻点全和可区别k-全染色.将所用的最少颜色数k称作G的邻点全和可区别全色数，简记为ftndi_Σ（G）.该文运用结构分析法完整刻画了双圈图G的邻点全和可区别全染色，得到了ftndi_Σ（G）=Δ（G）+1,从而验证了邻点全和可区别全染色猜想在双圈图上是成立的.