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 \(\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: 김재훈