The list r-hued coloring of trees and unicyclic graphs

Abstract

Let $r$ be a positive integer and $G$ be a graph. The list $r$-hued chromatic number of $G$, denoted by ${\chi }_{L,r}(G)$, is the smallest integer $k$, such that for each $k$-list $L$ of $G$, $G$ has an $(L,r)$-coloring. It is proved in [Discrete Math. 306 (16) (2006) 1997-2004] that every tree $G$ satisfies ${\chi }_r(G)=\min \{r,\Delta (G)\}+1$. It is known that every cycle graph $C_n$ with order $n$ has ${\chi }_{L,r}(C_n)={\chi }_r(C_n)$. The main results are the following: $(1)$ If $G$ is a tree, then ${\chi }_{L,r}(G)=\min \{r,\Delta (G)\}+1$; $(2)$ Let $G$ be a unicyclic graph which is not isomorphic to the cycle $C_n$. If $n\ne 5$ and $r\ge 3$, then ${\chi }_{L,r}(G)=\min \{r,\Delta (G)\}+1$; otherwise, $\min \{r,\Delta (G)\}+1\le {\chi }_{L,r}(G)\le \min \{r,\Delta (G)\}+2$.