Pewarnaan Packing Pada Famili Graf Pohon Dan Graf Hasil Operasi Amalgamasi Titik

Abstract

Topik graf pada penelitian ini adalah pewarnaan titik. Pewarnaan titik merupakan pemberian warna pada setiap titik dimana titik yang bertetangga harus mendapatkan warna yang berbeda. Bilangan asli seperti {1, 2, 3, ..., k} menunjukkan warna seminimal mungkin pada pewarnaan titik suatu graf G yang disebut sebagai bilangan kromatik chromatic number dan dinotasikan dengan χ(G). Pada penelitian ini menggunakan salah satu jenis pewarnaan titik yaitu pewarnaan packing. Pewarnaan packing merupakan pemberian warna pada titik misal terdapat dua buah titik yang tidak bertetangga yaitu titik x dan y diperoleh c(x) = c(y) = i dan d(x, y) ≥ i + 1. Bilangan asli yang menunjukkan warna seminimal mungkin pada pewarnaan packing suatu graf G disebut bilangan kromatik packing dan dinotasikan dengan χρ(G). Kemudian jenis penelitian ini adalah penelitian eksploratif. Latar belakang digunakannya jenis penelitian eksploratif adalah proses dari awal hingga akhir bertujuan untuk menemukan hal baru yang harapannya dapat digunakan sebagai dasar penelitian selanjutnya sedangkan metode penelitian yang digunakan adalah metode deduktif aksiomatik dan metode pendeteksi pola. Kedua metode tersebut mendukung proses penelitian ini karena untuk mendapatkan bilangan kromatik packing dibutuhkan proses pencarian pola pewarnaan packing setelah diperoleh bilangan kromatik packing maka membuat dan membuktikan teorema bilangan kromatik packing. Penelitian ini menghasilkan lima teorema tentang bilangan kromatik packing pada famili graf pohon dan tiga teorema tentang bilangan kromatik packing pada graf hasil operasi amalgamasi titik. Berikut teorema yang dihasilkan pada penelitian ini: Teorema 1 Bilangan kromatik packing pada graf centipede Cpn untuk n ≥ 2 adalah  3, untuk n = 2, 3 4, untuk 4 ≤ n ≤ 7 5, untuk n ≥ 8 Teorema 2 Bilangan kromatik packing pada graf kembang api Fm,n untuk m ≥ 2 dan n ≥ 3 adalah χρ(Fm,n ) =  3, untuk m = 2, 3 4, untuk 4 ≤ m ≤ 7 5, untuk m ≥ 8 Teorema 3 Bilangan kromatik packing pada graf sapu Bdn untuk d ≥ 3 dan n n d ≥ 2 adalah 3. Teorema 4 Bilangan kromatik packing pada graf bintang ganda Sm,n untuk m ≥ 2 dan n ≥ 2 adalah 3. Teorema 5 Bilangan kromatik packing pada graf pohon pisang Bm,n untuk n ≥ 3 dan m ≥ 2 adalah 3. Teorema 6 Bilangan kromatik packing pada graf hasil operasi amalgamasi titik graf lintasan amal(Pn, v, m) untuk n ≥ 2 dan m ≥ 2 adalah χρ(amal(Pn, v, m)) = ( 2, untuk n = 2 dan m ≥ 2 3, untuk n > 2 dan m ≥ 2 Teorema 7 Bilangan kromatik packing pada graf hasil operasi amalgamasi titik graf sapu amal(Bdn , v, m) untuk d ≥ 3, n n d ≥ 2 dan m ≥ 2 adalah 3. Teorema 8 Bilangan kromatik packing pada graf hasil operasi amalgamasi titik graf bintang amal(Sn, v, m) untuk n ≥ 3 dan m ≥ 2 adalah χρ(amal(Sn, v, m)) = ( 4, untuk m ≥ 2 dan n = 3 m + 1, untuk m ≥ 2 dan n > 3 i