最大度不大于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.

最大度为5的简单图的2-距离列表染色

通过对极小反例G的结构分析,利用权转移的方法,证明了:对于Δ(G)≤5的图G,若mad(G)<20/7,则χl2(G)≤10;若mad(G)<19/6,则χl2(G)≤11.这一结果改进了现有的部分结论.

不含短圈平面图的2-距离列表染色

图的染色理论在图论中有着重要的地位.主要运用权转移技巧,通过结构分析,研究了不含4-圈和5-圈的平面图的2-距离列表染色.降低了这类平面图的2-距离(Δ+4)-列表染色的最大度下界,证明了不含4-圈和5-圈且Δ≥12的平面图是2-距离(Δ+4)-列表可染的.