### Linear choosability of graphs

*Louis Esperet, Mickaël Montassier, André Raspaud*

#### Abstract

A proper vertex coloring of a non oriented graph G=(V,E) is

*linear*if the graph induced by the vertices of two color classes is a forest of paths. A graph G is L-list colorable if for a given list assignment L={L(v): v∈V}, there exists a proper coloring c of G such that c(v)∈L(v) for all v∈V. If G is L-list colorable for every list assignment with |L(v)|≥k for all v∈V, then G is said k-choosable. A graph is said to be lineary k-choosable if the coloring obtained is linear. In this paper, we investigate the linear choosability of graphs for some families of graphs: graphs with small maximum degree, with given maximum average degree, planar graphs... Moreover, we prove that determining whether a bipartite subcubic planar graph is lineary 3-colorable is an NP-complete problem.Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page