IJPAM: Volume 110, No. 4 (2016)

Title

$r$-DYNAMIC CHROMATIC NUMBER OF CYCLES,
COMPLETE GRAPHS AND FORESTS

Authors

Hermie V. Inoferio$^1$, Michael P. Baldado Jr.$^2$
$^1$College of Education
Jose Rizal Memorial State University
Katipunan, Zamboanga del Norte, PHILIPPINES
$^2$Mathematics Department
Negros Oriental State University
Dumaguete City, Philippines

Abstract

Let $G=\left(V,E\right)$ be a graph. An $r$-dynamic $k$-coloring of $G$ is a function $f$ from $V$ to a set $C$ of colors such that (1) $f$ is a proper coloring, and (2) for all vertices $v$ in $V$, $\left\vert f\left(N\left(v\right)\right)\right\vert\geq min\left\{r, deg_{G}\left(v\right)\right\}$. The $r$-dynamic chromatic number of a $G$, denoted by $\chi_{r} \left(G\right)$, is the smallest $k$ such that $f$ is an $r$-dynamic $k$-coloring of $G$.

This study gave the $r$-dynamic chromatic number of paths, cycles, complete graphs, empty graphs, the vertex gluing of graphs and the union of graphs. Some characterizations are also given.

History

Received: July 15, 2016
Revised: October 10, 2016
Published: November 9, 2016

AMS Classification, Key Words

AMS Subject Classification: 05C15
Key Words and Phrases: $r$-dynamic chromatic number, $r$-dynamic $k$-coloring, cycles, vertex gluing

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
H.J. Lai, B. Montgomery, H. Poon, Upper bounds of dynamic chromatic number, Ars Combin. 68 (2003) 193-201.

2
A. Taherkhani, $r$-Dynamic Chromatic Number of Graphs, arXiv:1401.6470v1 $\left[\text{math.CO}\right]$ 24 Jan 2014.

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

4
B. Gao, L. Sun, H. Sung, H.J. Lai, On the Difference Between Dynamic Chromatic and Chromatic Number of Graphs, Journal of Mathematical Sciences: Advances and Applications 34 (2015), 1-10.

5
Y. Chen, S. Fan, H.-J. Lai, H. Song, L. Sun, On dynamic coloring for planar graphs and graphs of higher genus, Discrete Applied Mathematics 160 (2012), 1064-1071.

6
Y. Kim, S.J. Lee, S.-I. Oum, Dynamic Coloring of Graphs Having No $K_{5}$ Minor, arXiv:1201.2142v3 $\left[\text{math.CO}\right]$ 15 March 2015.

7
M. Alishahi, On the dynamic coloring of graphs, Discrete Applied Mathematics 159 (2011) 152-156.

8
R. Kang, T. Muller, D.B. West, On $r$-dynamic coloring of grids, Discrete Applied Mathematics 186 (2015) 286-290.

9
S. Jahanbekam, J. Kim, Suil O, D.B. West, On $r$-dynamic coloring of graphs, submitted for publication.

10
H.-J. Lai, B. Montgomery, Dynamic coloring of graphs, West Virginia University, 2002.

11
Wikipedia contributors. "Graph coloring." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 30 Jun. 2016. Web. 8 Jul. 2016.

12
J. Gross, J. Yellen, Handbook of Graph Theory, CRC Press LLC, N. W., Corporate Blvd, Boca Raton, Florida, 2000.

How to Cite?

DOI: 10.12732/ijpam.v110i4.4 How to cite this paper?

Source:
International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2016
Volume: 110
Issue: 4
Pages: 609 - 622


$r$-DYNAMIC CHROMATIC NUMBER OF CYCLES, COMPLETE GRAPHS AND FORESTS%22&as_occt=any&as_epq=&as_oq=&as_eq=&as_publication=&as_ylo=&as_yhi=&as_sdtAAP=1&as_sdtp=1" title="Click to search Google Scholar for this entry" rel="nofollow">Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).