Skip to main content
Article
On r-dynamic coloring of graphs
Discrete Applied Mathematics (2016)
  • Sogol Jahanbekam, University of Colorado Denver
  • Jaehoon Kim, University of Birmingham
  • Suil O, Simon Fraser University
  • Douglas B. West, University of Illinois at Urbana–Champaign
Abstract
An r-dynamic properk-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 χr(G), is the least k such that G has such a coloring. By a greedy coloring algorithm, χr(G)≤rΔ(G)+1; we prove that equality holds for Δ(G)>2 if and only if G is r-regular with diameter 2 and girth 5. We improve the bound to χr(G)≤Δ(G)+2r−2 when δ(G)>2rlnn and χr(G)≤Δ(G)+r when δ(G)>r2lnn.
In terms of the chromatic number, we prove χr(G)≤rχ(G) when G is k-regular with k≥(3+o(1))rlnr and show that χr(G) may exceed r1.377χ(G) when k=r. We prove χ2(G)≤χ(G)+2 when G has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, χ2(G)≤3χ(G) when G has diameter 3, which is sharp. However, χ2 is unbounded on bipartite graphs with diameter 4, and χ3 is unbounded on bipartite graphs with diameter 3 or 3-colorable graphs with diameter 2. Finally, we study χr on grids and toroidal grids.
Keywords
  • Dynamic coloring,
  • Graph coloring
Publication Date
June 19, 2016
DOI
10.1016/j.dam.2016.01.016
Publisher Statement
SJSU users: use the following link to login and access the article via SJSU databases.
Citation Information
Sogol Jahanbekam, Jaehoon Kim, Suil O and Douglas B. West. "On r-dynamic coloring of graphs" Discrete Applied Mathematics Vol. 206 (2016) p. 65 - 72 ISSN: 0166-218X
Available at: http://works.bepress.com/sogol-jahanbekam/3/