## Jaehoon Kim, On r-dynamic coloring of graphs

On r-dynamic coloring of graphs
Jaehoon Kim
KAIST/Univ. of Birmingham, UK
2014/06/09 Monday 4PM-5PM
Room 1409
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)\le r\Delta(G)+1$$ and the equality holds if and only if G is r-regular with diameter 2 and girth 5. We improve the bound to $$\chi_r(G)\le \Delta(G)+2r$$ when $$\delta(G)\ge 2r\ln n$$. In terms of the chromatic number, we prove $$\chi_r(G)\le r\chi(G)$$ when G is k-regular with $$k \ge (3+o(1))r\ln r$$ and show that $$\chi_r(G)$$ may exceed $$r^{1.377}\chi(G)$$ when k=r. We prove $$\chi_2(G)\leq \chi(G)+2$$ when G has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, $$\chi_2(G)\le 3\chi(G)$$ when G has diameter 3, which is sharp. This is joint work with Sogol Jahanbekam, Suil O, and Douglas B. West.

Tags: