An r-dynamic proper k-coloring of a graph G is a proper k-coloring of G such that every vertex in V(G) has neighbors in at least min{d(v), r} different color classes. The r-dynamic chromatic number of a graph G, written chi(r)(G), is the least k such that G has such a coloring. By a greedy coloring algorithm, chi(r)(G) <= r Delta(G) + 1; we prove that equality holds for Delta(G) > 2 if and only if G is r-regular with diameter 2 and girth 5. We improve the bound to chi(r)(G) <= Delta(G) + 2r - 2 when delta(G) > 2r Inn and chi(r) (G) <= (G) + r when delta(G) > r(2) In n. In terms of the chromatic number, we prove X-r(G) < r chi (G) when G is k-regular with k >= (3 o(1))r In r and show that chi(r)(G) may exceed r(1.377) chi(G) when k = r. We prove chi(2) (G) <= chi (G) + 2 when G has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, chi(2)(G) <= 3 chi (G) when G has diameter 3, which is sharp. However, chi(2) is unbounded on bipartite graphs with diameter 4, and chi 3 is unbounded on bipartite graphs with diameter 3 or 3-colorable graphs with diameter 2. Finally, we study chi(r) on grids and toroidal grids. (C) 2016 Published by Elsevier B.V.

- Publisher
- ELSEVIER SCIENCE BV

- Issue Date
- 2016-06

- Language
- English

- Article Type
- Article

- Citation
DISCRETE APPLIED MATHEMATICS, v.206, pp.65 - 72

- ISSN
- 0166-218X

- Appears in Collection
- MA-Journal Papers(저널논문)

- Files in This Item
- There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.