报告题目：r-hued coloring of P_t free graphs

报告人： 中国人民大学吕雪征 副教授

报告时间：2018年9月8日（周六）9: 00-10: 00

报告地点：英国威廉希尔体育公司201学术报告厅

报告摘要：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.