On r-dynamic coloring of graphs

Cited 19 time in webofscience Cited 0 time in scopus
  • Hit : 80
  • Download : 0
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
DOI
10.1016/j.dam.2016.01.016
URI
http://hdl.handle.net/10203/263346
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 19 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0