稀疏图的k-frugal列表染色

k-frugal List Coloring of Sparse Graphs

摘要:

图G的k-frugal列表色数一般记作chkG，关于稀疏的k-frugal列表色数上界，有以下3个结论：? k≥3，如果图G满足madG<3-a（其中0<a≤13）且ΔG≥k+3a-3，则chkG=?k-1+1；? k≥4，如果图G满足madG<3，则chkG≤?k-1+2；? k≥4，如果图G满足madG<103，则chkG≤?k-1+3。

Abstract:

The k-frugal choice number of graph G is denoted by chk(G). In this paper， we prove the following theorem. Let G be a graph with maximum average degree madG<3-a (0<a≤13) and maximum degreeΔG≥k+3a-3， then chkG=?k-1+1 for any integer k≥3； Let G be a graph with maximum average degree madG<3， then chkG≤?k-1+2 for any integer k≥4； Let G be a graph with maximum average degree madG<103， then chkG≤?k-1+3 for any integer k≥4.