TY - JOUR
ID - 400
TI - k-forested choosability of graphs with bounded maximum average degree
JO - Bulletin of the Iranian Mathematical Society
JA - BIMS
LA - en
SN - 1017-060X
AU - Zhang, X.
AU - Liu, G.
AU - Wu, J. L.
AD - Xidian University
AD - Shandong University
Y1 - 2012
PY - 2012
VL - 38
IS - 1
SP - 193
EP - 201
KW - k-forested coloring
KW - linear coloring
KW - maximum average degree
DO -
N2 - 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.
UR - http://bims.iranjournals.ir/article_400.html
L1 - http://bims.iranjournals.ir/article_400_33c983c4321f08451943d77a341f126b.pdf
ER -