Pewarnaan Metrik pada Graf Kincir Angin Belanda, Graf Petersen Diperumum, Graf Blossom,Graf Tangga Permata, dan E-Monografnya

Abstract

Graf didefinisikan sebagai pasangan terurut (V, E), dengan V merupakan himpunan tak kosong yang elemen-elemennya disebut titik (vertices), sedangkan E merupakan himpunan sisi yang berhingga dan dapat berupa himpunan kosong. Setiap sisi menghubungkan dua titik berbeda pada graf G. Pewarnaan metrik (metric coloring) didefinisikan sebagai berikut. Misalkan f: V(G) → {1, 2, 3, ..., k} merupakan pewarnaan titik pada graf G, dengan dua titik yang bertetangga diperbolehkan memiliki warna yang sama. Misalkan Π = {C₁, C₂, ..., Cₖ} merupakan himpunan kelas warna. Representasi warna suatu titik v ∈ V(G) didefinisikan sebagai vektor-k berikut: r(v|Π) = (d(v,C₁), d(v,C₂), ..., d(v,Cₖ)), dengan d(v,Cᵢ) = min{d(v,u) : u ∈ Cᵢ}. Jika r(u|Π) ≠ r(v|Π) untuk setiap dua titik bertetangga u dan v pada graf G, maka pewarnaan tersebut disebut pewarnaan metrik pada graf G. Dengan demikian, dua titik bertetangga dapat diberi warna yang sama apabila representasi warna atau kode metrik kedua titik tersebut berbeda. Tujuan penelitian ini adalah menentukan bilangan kromatik metrik (metric chromatic number). Graf yang dikaji meliputi graf Dutch windmill, graf Petersen tergeneralisasi dengan lompatan sisi (side jumps) bernilai satu, graf blossom, dan graf diamond ladder. Graf-graf tersebut dipilih karena belum ditemukan penelitian terdahulu yang secara khusus membahas pewarnaan metrik pada graf-graf tersebut. Pembuktian dilakukan dengan menentukan batas bawah bilangan kromatik metrik, kemudian menentukan batas atas melalui konstruksi fungsi pewarnaan. Selanjutnya, sifat pewarnaan metrik diperiksa dengan menunjukkan bahwa representasi warna setiap pasangan titik yang bertetangga berbeda.