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

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.



Copyright ? 2013 isg. hubu.edu.cn All Rights Reserved.    

Address: No. 368, Friendship Avenue, Wuchang District, Wuhan, Hubei. Zip code: 430062

Email:stxy@hubu.edu.cn phone: 027-88662127