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

LIST 2-DISTANCE COLORING OF GRAPHS WITH MAXIMUM DEGREE NO MORE THAN 5

图的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.

The 2-distance coloring of graph can be used in channel assignment of wireless communication network.We study the 2-distance coloring problem of general graphs under the condition of maximum degree and maximum average degree.We prove that if a graph G satisfiesΔ(G)≤5,mad(G)<2+43/100 and every 5-vertex in G adjacent to at least one 3^(+)-vertex then ^(2)_(l)(G)≤6.Firstly,we analyze the minimal counterexample to get some reducible configuration.Then we design the rules of discharging and use some properties.Finally,we use discharging method to prove our result in the case of keeping the sum of weights the same.The result we get can improve the result gotten by Cranston et al.in 2014:if a graph G satisfiesΔ(G)≤5,mad(G)<2+12/29,then ^(2)_(l)l(G)≤6.