Linear choosability of graphs

A proper vertex coloring of a non-oriented graph G is linear if the graph induced by the vertices of any two color classes is a forest of paths. A graph G is linearly L  -list colorable if for a given list assignment L={L(v):v∈V(G)}L={L(v):v∈V(G)}, there exists a linear coloring c of G   such that c(v)∈L(v)c(v)∈L(v) for all v∈V(G)v∈V(G). If G is linearly L  -list colorable for any list assignment with |L(v)|⩾k|L(v)|⩾k for all v∈V(G)v∈V(G), then G is said to be linearly k-choosable. In this paper, we investigate the linear choosability for some families of graphs: graphs with small maximum degree, with given maximum average degree, outerplanar and planar graphs. Moreover, we prove that deciding whether a bipartite subcubic planar graph is linearly 3-colorable is an NP-complete problem.