k-frugal List Coloring of Sparse Graphs

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.