On r-dynamic coloring of some graph operations

Ika Hesti Agustin, D. Dafik, A. Y. Harsya

Abstract


Let $G$ be a simple, connected and undirected graph. Let $r,k$ be natural number. By a proper $k$-coloring  of a graph $G$, we mean a map $ c : V (G) \rightarrow 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))| \geq 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 \in S\}$ for a vertex subset $S$ . The $r$-dynamic chromatic number, written as $\chi_r(G)$, is the minimum $k$ such that $G$ has an $r$-dynamic $k$-coloring. Note that the $1$-dynamic chromatic number of graph is equal to its chromatic number, denoted by $\chi(G)$, and the $2$-dynamic chromatic number of graph has been studied under the name a dynamic chromatic number, denoted by $\chi_d(G)$. By simple observation it is easy to see that $\chi_r(G)\le \chi_{r+1}(G)$, however $\chi_{r+1}(G)-\chi_r(G)$ can be arbitrarily large, for example $\chi(Petersen)=2, \chi_d(Petersen)=3$, but $\chi_3(Petersen)=10$. Thus, finding an exact values of $\chi_r(G)$ is significantly useful. In this paper, we will show some exact values of $\chi_r(G)$ when $G$ is an operation of special graphs.

Keywords


r-dynamic coloring; r-dynamic chromatic number; graph operations.

Full Text:

PDF

References


J.L. Gross, J. Yellen and P. Zhang, Handbook of Graph Theory, Second Edition, CRC Press, Taylor and Francis Group, 2014

S.J. Kim and W.J. Park, List dynamic coloring of sparse graphs, Combinatorial optimization and applications. Lect. Notes Comput. Sci. 6831 (Springer, 2011), 156– 162.

S.J. Kim, S. J. Lee, and W.J. Park, Dynamic coloring and list dynamic coloring of planar graphs. Discrete Applied Math. 161 (2013), 2207–2212.

S. Akbari, M. Ghanbari, S. Jahanbekam, On the dynamic chromatic number of graphs, Combinatorics and graphs. Contemp. Math. 531 (Amer. Math. Soc. 2010), 1–18.

B. Montgomery, Dynamic Coloring of Graphs. Ph.D Dissertation, West Virginia University, 2001.

H.J. Lai, B. Montgomery, and H. Poon, Upper bounds of dynamic

chromatic number. Ars Combin. 68 (2003), 193–201.

S Jahanbekam, J Kim, O Suil, D.B. West, On r-dynamic Coloring of Graphs, 2014, In Press

R.L. Brooks, On colouring the nodes of a network. Proc. Cambridge Philos. Soc. 37 (1941), 194–197.




DOI: http://dx.doi.org/10.19184/ijc.2016.1.1.3

Refbacks

  • There are currently no refbacks.


ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats