Upper bounds of r-hued colorings of planar graphs

作者：Song, Huimin; Lai, Hong-Jian^*

来源：Discrete Applied Mathematics, 2018, 243: 262-269.

DOI：10.1016/j.dam.2017.12.041

• (k, r)-coloring
• r-hued coloring
• r-hued chromatic number
• Dynamic coloring
• Dynamic chromatic number
• Planar graph

For positive integers k and r, a (k, r)-coloring of a graph G is a proper k-coloring of the vertices such that every vertex of degree d is adjacent to vertices with at least min{d, r} different colors. The r-hued chromatic number of a graph G, denoted by chi(r)(G), is the smallest integer k such that G has a (k, r)-coloring. In Song et al. (2014), it is conjectured that if r >= 8, then every planar graph G satisfies chi(r)(G) <= (left perpendicular) 3r/2(right perpendicular) + 1. Wegner in 1977 conjectured that the above-mentioned conjecture holds when r = Delta(G). This conjecture, if valid, would be best possible in some sense. In this paper, we prove that, if G is a planar graph and r >= 8, then chi(r)(G) <= 2r + 16.

• 出版日期2018-7-10
• 单位山东大学