List -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 , a -coloring of a graph is a proper coloring with at most colors such that for any vertex with degree , there are at least min different colors present at the neighborhood of . The -hued chromatic number of , , is the least integer such that a -coloring of exists. The list-hued chromatic number of is similarly defined. Thus if , then . We present examples to show that, for any sufficiently large integer , there exist graphs with maximum average degree less than 3 that cannot be -colored. We prove that, for any fraction , there exists an integer such that for each , every graph with maximum average degree is list -colorable. We present examples to show that for some there exist graphs with maximum average degree less than 4 that cannot be -hued colored with less than colors. We prove that, for any sufficiently small real number , there exists an integer such that every graph with maximum average degree satisfies . These results extend former results in Bonamy et al. (2014). |
| |
Keywords: | Maximum average degree Square coloring |
本文献已被 ScienceDirect 等数据库收录! |
|