Linear list colorings of graphs with maximum average degrees bounded

摘要

A graph G is linearly L-colorable if there is a linear coloring c of G for a given list assignment L = {L(v) : v is an element of V(G)} such that c(v) is an element of L(v) for all v is an element of V(G), and G is linearly k-choosable if G is linearly L-colorable for any list assignment with vertical bar L(v)vertical bar >= k. The smallest integer k such that G is linearly k-choosable is called the linear list chromatic number, denoted by l(Cl)(G). It is clear that l(Cl)(G) >= [Delta(G)/2] + 1 for any graph G with maximum degree Delta(G). The maximum average degree of a graph G, denoted by mad(G), is the maximum of the average degrees of all subgraphs of G. In this note, we shall show: (1) If mad(G) < 3, then l(Cl)(G) < [Delta(G)/2] + 3; (2) If mad(G) < 17/6 and Delta(G) >= 5, then l(Cl)(G) <= [Delta(G)/2] + 2; (3) If mad(G) < 14/5 and Delta(G) >= 13, then l(Cl)(G) = [Delta(G)/2] + 1.