NILAI KROMATIK PEWARNAAN SISI r-DINAMIS PADA GRAF EKSPONENSIAL DAN GRAF OPERASI

Abstract

Teori graf merupakan salah satu topik matematika yang banyak dikaji oleh peneliti, salah satu topik dalam teori graf yang sering diteliti yaitu pewarnaan graf. Pewarnaan graf digolongkan menjadi pewarnaan titk (vertex coloring), pe- warnaan sisi (edge coloring), dan pewarnaan wilayah (region coloring). Pada perkembangannya pewarnaan graf telah mengalami variasi, diantaranya yaitu pe- warnaan dinamis yang dikembangkan oleh Bruce Montgomery pada tahun 2001. Pewarnaan k-warna dinamis pada graf G merupakan pewarnaan titik pada graf G sebanyak k warna sedemikian hingga setiap titik berderajat minimum dua pada G memiliki dua warna berbeda dengan titik-titik ketetanggaannya. Nilai k warna pada graf G yang memiliki k-warna dinamis disebut dengan bilangan kromatik dinamis, disimbolkan dengan Âd(G). Pewarnaan titik r-dinamis kemudian digene- ralisasiakan menjadi pewarnaan titik r-dinamis. Pewarnaan titik r-dinamis pada akhirnya mengalami perkembangan yaitu pewarnaan sisi r-dinamis yang disesuaikan dengan kondisi/syarat pada pewar- naan sisi graf. Pewarnaan sisi r-dinamis pada suatu graf G dide¯nisikan seba- gai pemetaan c dari E(G) ke himpunan warna sedemikian hingga jc(N(e))j ¸ minfr; d(u) + d(v) ¡ 2g untuk setiap e = uv 2 E(G), dimana N(e) merupakan himpunan sisi yang bersisian dengan sisi e, dan d(u) merupakan derajat dari titik u. Penggunaan k-warna dinamis yang paling minimal disebut dengan bilangan kromatik sisi r dinamis yang dinotasikan dengan ¸r(G). Pewarnaan sisi r-dinamis dapat diterapkan pada hasil operasi dari graf beberapa graf khusus, misalnya seperti hasil operasi graf cycle, windmill, star, stecked book, dan triangular book. Sedangkan operasi graf adalah suatu metode yang digunakan untuk memproleh graf baru dengan cara mengombinasikan dua graf atau lebih .