k-FORESTED CHOOSABILITY OF GRAPHS WITH BOUNDED MAXIMUM AVERAGE DEGREE

A proper vertex coloring of a simple graph is k-forested if the graph induced by the vertices of any two color classes is a forest with maximum degree less than k. A graph is k-forested qchoosable if for a given list of q colors associated with each vertex v, there exists a k-forested coloring of G such that each vertex receives a color from its own list. In this paper, we prove that the k-forested choosability of a graph with maximum degree ∆ ≥ k ≥ 4 is at most [∆/k−1] + 1, [∆/k−1] + 2 or [∆/k−1] + 3 if its maximum average degree is less than 12/5 , 8/3 or 3, respectively.