最大度不大于5的图的2距离列表染色

图的2距离染色在无线通讯网络信道分配中有着十分广泛的应用.本文旨在探究最大度与最大平均度条件下的一般图的2距离染色问题.首先通过分析极小反例,得到了某些可约构型,之后设计了权转移规则,利用得到的结构性质,在保持权总和不变的情况下进行权转移.本文证明了下述结论成立:若图G满足Δ(G)≤5,mad(G)<2+43/100,且图G的每个5-点至少相邻一个3^(+)-点,则χ^(2)_(l)(G)≤6.该结论扩展了Cranston等人在2014年的结论:若图G满足Δ(G)≤5,mad(G)<2+12/29,则^(2)_(l)(G)≤6.