LIST POINT ARBORICITY OF GRAPHS
Nini Xue, Baoyindureng Wu · Discrete Mathematics Algorithms and Applications · 2012
Let G be a graph. The point arboricity of G, denoted by ρ(G), is the minimum number of colors that can be used to color the vertices of G so that each color class induces an acyclic subgraph of G. Borodin et al. (Discrete Math.214 (2000) 101–112) first introduced the list point arboricity of G, denoted by ρl(G). We prove that for any graph G, [Formula: see text], where deg (G) denotes the degeneracy of G, that is, the minimum number k such that δ(H) ≤ k for any subgraph H of G. Using this upper bound, we show that ρl(G) ≤ 3 for any planar graph G. In particular, if either G is K4-minor free, or for an integer k ∈ {3, 4, 5, 6}, G is planar and does not contain k-cycles, then ρl(G) ≤ 2. For any graph G of order n, [Formula: see text]. In addition, we provide a new proof of a theorem of Borodin et al., which states that if G is neither a complete graph of odd order nor a cycle then [Formula: see text]. Finally, we show that la (G) = lla (G) = 2 if G is 3-regular, and la (G) = lla (G) = 3 if G is 4-regular, where la (G) is the linear arboricity of G and lla (G) is list linear arboricity of G which is introduced recently by An and Wu.