澳门新葡新京,澳门新葡新京官方网站

欢迎来到:澳门新葡新京!

学术报告
当前位置: 澳门新葡新京 > 学术报告 > 正文
r-hued coloring of P_t free graphs
编辑:      澳门新葡新京:2018-09-05       点击数:
报告时间 2018年9月8日09:00-10:00 报告地点 澳门新葡新京201报告厅
报告人 吕雪征(中国人民大学)

报告题目: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.


Copyright ©版权所有:澳门新葡新京

地址:湖北省武汉市武昌区友谊大道368号 邮政编码:430062

Email:stxy@hubu.edu.cn 电话:027-88662127

XML 地图 | Sitemap 地图