Pewarnaan Graceful pada Graf Petersen Diperumum

Abstract

Topik yang dijadikan sebagai kajian dalam skripsi ini adalah satu dari sekian banyak topik dalam bidang teori graf, khususnya dalam bidang pewarnaan graf, yaitu pewarnaan graceful. Pewarnaan dasar graf terdiri atas pewarnaan titik, sisi, dan wilayah. Pewarnaan titik adalah pemberian warna setiap titik pada suatu graf sedemikian hingga titik yang saling bertetangga (adjacent) diberi warna yang berbeda. Pewarnaan sisi adalah pemberian warna setiap sisi pada graf sedemikian hingga sisi yang saling bertetangga (adjacent) diberi warna yang berbeda. Pewarnaan wilayah adalah pemberian warna setiap wilayah pada graf sedemikian hingga wilayah yang saling bertetangga diberi warna yang berbeda. Pewarnaan graceful adalah bentuk pewarnaan titik yang nantinya menginduksi pewarnaan sisi nya melalui selisih positif dua buah titik yang saling bertetangga. k-pewarnaan graceful dari graf G adalah pewarnaan titik proper yang menginduksi pewarnaan sisi propernya melalui selisih dari dua warna titik yang membentuk sisi. Pewarnaan titik proper c dari graf G adalah pewarnaan graceful jika c adalah k-pewarnaan graceful untuk ݇k elemen dari N. Bilangan kromatik graceful dari graf G dilambangkan dengan x_G(g), adalah nilai k minimal dimana graf G memiliki k-pewarnaan graceful. Graf yang digunakan dalam penelitian ini adalah graf petersen diperumum dengan nilai lompatan sisi dalam dari 1 sampai dengan 4. Tujuan dari penelitian ini adalah untuk menemukan pola pewarnaan graceful untuk mencari bilangan kromatiknya pada graf petersen diperumum dengan batasan permasalahan yaitu nilai lompatan sisi bagian dalam yaitu dari 1 sampai dengan 4.