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\geq k\geq 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.