On r-dynamic coloring of graphs
Jaehoon Kim
KAIST/Univ. of Birmingham, UK
KAIST/Univ. of Birmingham, UK
2014/06/09 Monday 4PM-5PM
Room 1409
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 
different color classes. The r-dynamic chromatic number of a graph G, written 
, is the least k such that G has such a coloring. By a greedy coloring algorithm, 
and the equality holds if and only if G is r-regular with diameter 2 and girth 5. We improve the bound to 
when 
. In terms of the chromatic number, we prove 
when G is k-regular with 
and show that may exceed 
when k=r. We prove 
when G has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, 
when G has diameter 3, which is sharp. This is joint work with Sogol Jahanbekam, Suil O, and Douglas B. West.
different color classes. The r-dynamic chromatic number of a graph G, written , is the least k such that G has such a coloring. By a greedy coloring algorithm, and the equality holds if and only if G is r-regular with diameter 2 and girth 5. We improve the bound to when . In terms of the chromatic number, we prove when G is k-regular with and show that may exceed when k=r. We prove when G has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, when G has diameter 3, which is sharp. This is joint work with Sogol Jahanbekam, Suil O, and Douglas B. West.