Several classes of graphs and theirr-dynamic chromatic numbers
Dafik Dafik, Devi Eka Wardani Meganingtyas, Kosala Dwidja Purnomo, M. Dicky Tarmidzi, Ika Hesti Agustin · Journal of Physics Conference Series · 2017
Let G be a simple, connected and undirected graph. Let r, k be natural numbers. By a proper k -coloring of a graph G , we mean a map c : V ( G ) → S , where | S | = k , such that any two adjacent vertices receive different colors. An r -dynamic k -coloring is a proper k -coloring c of G such that | c ( N ( v ))| ≥ min{r, d ( v )} for each vertex v in V ( G ), where N ( v ) is the neighborhood of v and c ( S ) = {c ( v ) : v ∈ S } for a vertex subset S . The r -dynamic chromatic number, written as χ r ( G ), is the minimum k such that G has an r -dynamic k -coloring. By simple observation it is easy to see that χ r ( G ) ≤ χ r +1 ( G ), however χ r +1 ( G ) − χ r ( G ) does not always show a small difference for any r . Thus, finding an exact value of χ r ( G ) is significantly useful. In this paper, we will study some of them especially when G are prism graph, three-cyclical ladder graph, joint graph and circulant graph.