k-forested choosability of graphs with bounded maximum average degree

Abstract

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 $q$-choosable 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 $Deltageq kgeq 4$ is at most $leftlceilfrac{Delta}{k-1}rightrceil+1$, $leftlceilfrac{Delta}{k-1}rightrceil+2$ or $leftlceilfrac{Delta}{k-1}rightrceil+3$ if its maximum average degree is less than $frac{12}{5}$, $frac{8}{3}$ or $3$, respectively.