List strong linear 2‐arboricity of sparse graphs

A graph G is called ( k, j )‐colorable if the vertex set of G can be partitioned into subsets V 1 and V 2 such that the graph G [ V i ] induced by the vertices of V i has maximum degree at most k for i = 1 and at most j for i = 2. In particular, Havet and Sereni [2006] proved that each planar graph G is list (1, 1)‐colorable if its girth, g ( G ), is at least 8 and list (2, 2)‐colorable if g ( G )⩾6. Borodin et al. [2009] proved that every planar graph is (2, 1)‐colorable if g ( G )⩾7 and (5, 1)‐colorable if g ( G )⩾6. In fact, all these results were proved for each not necessarily planar sparse graph G , i.e. having a low maximum average degree, mad ( G ), over all subgraphs. A graph is a strong linear forest if its every connected component is a path of at most three vertices. Note that at most one third of the vertices in a strong linear forest have degree 2. We prove that each planar graph G with g ( G )⩾7 can be partitioned into two strong linear forests. The same is true for each graph G with g ( G )⩾7 and , and we actually prove a choosability version of this result. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:83‐90, 2011