Pewarnaan harmonis pada beberapa kelas graf berarah - Nurul Jannah; Nilamsari Kusumastuti; Meliana Pasaribu (Universitas PGRI Semarang, 2023)
AbstrakPewarnaan graf merupakan suatu pemetaan dari elemen pada suatu graf ke himpunan semua bilangan asli sedemikian sehingga setiap elemen yang bertetangga tidak dipetakan ke bilangan yang sama. Pada pewarnaan graf, image dari elemen suatu graf disebut warna. Dimisalkan dan adalah simpul-simpul pada dan serta adalah warna. Jika simpul diwarnai dengan dan simpul diwarnai dengan maka pasangan warna yang dihasilkan adalah pasangan warna . Pewarnaan harmonis menerapkan konsep pewarnaan simpul dalam mewarnai suatu graf dengan syarat satu pasang warna muncul paling banyak satu kali. Banyak warna yang paling minimum yang digunakan dalam pewarnaan harmonis disebut bilangan kromatik harmonis. Dalam penelitian ini, konsep pewarnaan harmonis akan diterapkan pada beberapa kelas graf berarah untuk melihat pola bilangan kromatik dari masing-masing kelas tersebut. Seperti diketahui, pada graf berarah , pasangan warna sehingga proses pewarnaan tersebut menjadi lebih kompleks. Adapun kelas graf yang dibahas adalah graf lili berarah , graf komplit berarah dan graf kipas berarah . Didapat bilangan kromatik harmonis pada graf lili berarah adalah dengan ; bilangan kromatik harmonis pada graf komplit berarah adalah . Sedangkan bilangan kromatik harmonis pada pewarnaan graf kipas berarah berada pada selang .Kata kunci: bilangan kromatik harmonis; pasangan warna; pewarnaan simpul