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 $\Delta \ge k\ge 4$ is at most $\lceil \frac{\Delta }{k-1}\rceil +1$, $\lceil \frac{\Delta }{k-1}\rceil +2$ or $\lceil \frac{\Delta }{k-1}\rceil +3$ if its maximum average degree is less than 12/5, $8/3 or 3, respectively.

Please cite this paper in press as X. Zhang, G. Liu, J.-L. Wu, k-forested choosability of graphs with bounded maximum average degree, Bulletin of the Iranian Mathematical Society, to appear