Zhang, X., Liu, G., Wu, J. (2012). k-forested choosability of graphs with bounded maximum average degree. Bulletin of the Iranian Mathematical Society, 38(1), 193-201.

X. Zhang; G. Liu; J. L. Wu. "k-forested choosability of graphs with bounded maximum average degree". Bulletin of the Iranian Mathematical Society, 38, 1, 2012, 193-201.

Zhang, X., Liu, G., Wu, J. (2012). 'k-forested choosability of graphs with bounded maximum average degree', Bulletin of the Iranian Mathematical Society, 38(1), pp. 193-201.

Zhang, X., Liu, G., Wu, J. k-forested choosability of graphs with bounded maximum average degree. Bulletin of the Iranian Mathematical Society, 2012; 38(1): 193-201.

k-forested choosability of graphs with bounded maximum average degree

Receive Date: 21 April 2010,
Revise Date: 27 September 2010,
Accept Date: 27 September 2010

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