Linear choosability of sparse graphs

A linear coloring is a proper coloring such that each pair of color classes induces a union of disjoint paths. We study the linear list chromatic number, denoted lcℓ(G), of sparse graphs. The maximum average degree of a graph GG, denoted mad(G)mad(G), is the maximum of the average degrees of all subgraphs of GG. It is clear that any graph GG with maximum degree Δ(G)Δ(G) satisfies lcℓ(G)≥⌈Δ(G)/2⌉+1. In this paper, we prove the following results: (1) if mad(G)<12/5 and Δ(G)≥3Δ(G)≥3, then lcℓ(G)=⌈Δ(G)/2⌉+1, and we give an infinite family of examples to show that this result is best possible; (2) if mad(G)<3 and Δ(G)≥9Δ(G)≥9, then lcℓ(G)≤⌈Δ(G)/2⌉+2, and we give an infinite family of examples to show that the bound on mad(G) cannot be increased in general; (3) if GG is planar and has girth at least 5, then lcℓ(G)≤⌈Δ(G)/2⌉+4.