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

Welcome to Faculty of Mathematics and Statistics

R-hued coloring of P_t free graphs
Author： Release time：2018-09-05 Number of clicks：

Title: R-hued coloring of P_t free graphs

Speaker: Xuezheng Lv

Affiliation: Renmin University of China

Time: 2018-9-8 09：00-10：00

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.