首页 | 本学科首页   官方微博 | 高级检索  
     检索      


List r-hued chromatic number of graphs with bounded maximum average degrees
Authors:Huimin Song  Hong-Jian Lai  Jianliang Wu
Institution:1. School of Mathematics and Statistics, Shandong University, Weihai 264209, PR China;2. Department of Mathematics, West Virginia University, Morgantown, WV 26506-6310, USA;3. School of Mathematics, Shandong University, Jinan 250100, PR China
Abstract:For integers k,r>0, a (k,r)-coloring of a graph G is a proper coloring c with at most k colors such that for any vertex v with degree d(v), there are at least min{d(v),r} different colors present at the neighborhood of v. The r-hued chromatic number of G, χr(G), is the least integer k such that a (k,r)-coloring of G exists. The listr-hued chromatic numberχL,r(G) of G is similarly defined. Thus if Δ(G)r, then χL,r(G)χr(G)r+1. We present examples to show that, for any sufficiently large integer r, there exist graphs with maximum average degree less than 3 that cannot be (r+1,r)-colored. We prove that, for any fraction q<145, there exists an integer R=R(q) such that for each rR, every graph G with maximum average degree q is list (r+1,r)-colorable. We present examples to show that for some r there exist graphs with maximum average degree less than 4 that cannot be r-hued colored with less than 3r2 colors. We prove that, for any sufficiently small real number ?>0, there exists an integer h=h(?) such that every graph G with maximum average degree 4?? satisfies χL,r(G)r+h(?). These results extend former results in Bonamy et al. (2014).
Keywords:Maximum average degree  Square coloring
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号