Venue: Room 201 Lecture Hall
abstract：For integers $k,r>0$, a $(k,r)$-coloring of a graph $G$ is a proper coloring on the vertices of $G$ with $k$ colors such that every vertex $v$ of degree $d(v)$ is adjacent to vertices with at least $\min\{d(v),r\}$ different colors. The $r$-hued chromatic number, denoted by $\chi_r(G)$, is the smallest integer $k$ for which a graph $G$ has a $(k,r)$-coloring. We prove the following.
(i) If $G$ is a $P_4$-free graph, then $\chi_r(G)\leq \chi(G)+2(r-1)$, and this bound is best possible.
(ii) If $G$ is a $P_5$-free bipartite graph, then $\chi_r(G)\le r\chi(G)$, and this bound is best possible.
(iii) If $G$ is a $P_5$-free graph, then $\chi_2(G)\le 2\chi(G)$, and this bound is best possible.
