Résumé
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 epsilon V(G)}, there exists a linear coloring c of G such that c(v) epsilon L(v) for all v epsilon V(G). If G is linearly L-list colorable for any list assignment with vertical bar L(v)vertical bar >= k for all V E 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. (C) 2007 Elsevier B.V. All rights reserved.