”Analisis Vertex r-Dynamic Coloring pada Beberapa Graf Khusus

Abstract

Teori graf berkembang sangat pesat, perkembangan yang sangat pesat membuat banyak topik-topik yang dapat dikaji dalam teori graf, salah satu topiknya adalah pe- warnaan. Macam-macam pewarnaan yang dapat dikaji dalam teori graf yaitu pewar- naan titik (Vertex Coloring), pewarnaan sisi (Edge Coloring), dan pewarnaan total (To- tal Coloring). Pewarnaaan titik adalah pewarnaan yang diberikan kepada titik-titik graf. Pewarnaan sisi adalah pewarnaan yang diberikan kepada sisi-sisi graf. Sedangkan pe- warnaan total adalah pewarnaan yang diberikan pada titik dan sisi graf. Pewarnaan pada graf haruslah berbeda di mana tidak boleh ada warna sama yang berdekatan namun pewarnaan haruslah seminimum mungkin disebut bilangan kromatik biasanya dino- tasikan (G). Topik-topik yang dapat dikaji dalam lingkup pewarnaan, salah satunya adalah topik dari perwarnaan titik adalah pewarnaan titik r-dinamis yang dinotasikan dengan r(G). Pewarnaan titik r-dinamis pada graf G adalah pemetaan c : V (G) → (1; 2; : : : ; k), dengan kata lain pewarnaan titik r-dinamis adala pemetaan himpunan titik graf G ke himpunan warna sedemikian hingga memenuhi kondisi |c(N(v))| ≥ min{r; d(vi)}.