Brooks-type theorem for $r$-hued coloring of graphs

An $r$-hued coloring of a simple graph $G$ is a proper coloring of its vertices such that every vertex $v$ is adjacent to at least $\min \{r,\mathrm{°}(v)\}$ differently colored vertices. The minimum number of colors needed for an $r$-hued coloring of a graph $G$, the $r$-hued chromatic number, is denoted by ${\chi }_r(G)$. In this note we show that $${\chi }_r(G)\le (r-1)(\mathrm{\Delta }(G)+1)+2,$$ for every simple graph $G$ and every $r\ge 2$, which in the case when $r<\mathrm{\Delta }(G)$ improves the presently known $\mathrm{\Delta }(G)$-based upper bound on ${\chi }_r(G)$, namely $r\mathrm{\Delta }(G)+1$. We also discuss the existence of graphs whose $r$-hued chromatic number is close to $(r-1)(\mathrm{\Delta }+1)+2$ and we prove that there is a bipartite graph of maximum degree $\mathrm{\Delta }$ whose $r$-hued chromatic number is $(r-1)\mathrm{\Delta }+1$ for every $r\in \{2,\dots ,9\}$ and infinitely many values of $\mathrm{\Delta }\ge r+2$; we believe that $(r-1)\mathrm{\Delta }(G)+1$ is the best upper bound on the $r$-hued chromatic number of any bipartite graph $G$.