Linear list r-hued coloring of sparse graphs

An r-hued coloring is a proper coloring such that the number of colors used by the neighbors of v is at least min{r,d(v)}. A linear r-hued coloring is an r-hued coloring such that each pair of color classes induces a union of disjoint paths. We study the linear list r-hued chromatic number, denoted by χL,rl(G), of sparse graphs. It is clear that any graph G with maximum degree Δ(G) ≥ r satisfies χL,rl(G) ≥max{⌈Δ/2⌉,r} + 1. Let mad(G) be the maximum average degree of a graph G. In this paper, we obtain the following results: (1)If mad(G) < 12 5, then χL,rl(G) ≤ max{⌈Δ/2⌉ + 1,r + 1},r ≥ 6; max{⌈Δ/2⌉ + 1, 7}, r = 5; max{⌈Δ/2⌉ + 1, 6}, 1 ≤ r ≤ 4. (2)If mad(G) < 5 2, then χL,rl(G) ≤max{⌈Δ/2⌉ + 1,r + 2, 7}. (3)If mad(G) < 8 3, then χL,rl(G) ≤max{⌈Δ/2⌉ + 2,r + 3, 8}.