Premium
List strong linear 2‐arboricity of sparse graphs
Author(s) -
Borodin Oleg V.,
Ivanova Anna O.
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20516
Subject(s) - combinatorics , arboricity , mathematics , planar graph , graph power , bound graph , graph , vertex (graph theory) , path graph , discrete mathematics , complement graph , line graph
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