Bilangan Kromatik Pewarnaan Titik pada Graf Dual dari Graf Roda

Muhammad Abdy; Rahmat Syam; T. Tina

doi:10.35580/jmathcos.v4i2.24443

Bilangan Kromatik Pewarnaan Titik pada Graf Dual dari Graf Roda

Muhammad Abdy^(1*), Rahmat Syam⁽²⁾, T. Tina⁽³⁾,

(1) Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Makassar
(2) Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Makassar
(3) Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Makassar
(*) Corresponding Author

DOI: https://doi.org/10.35580/jmathcos.v4i2.24443

Abstract

Penelitian ini bertujuan mengkonstruksi graf dual dari graf roda (W_n*) dan menentukan bilangan kromatik graf dual dari graf roda (W_n*). Penelitian ini dimulai dari menggambarkan beberapa graf roda dari ke , kemudian membangun graf dual dari graf roda dengan memanfaatkan graf-graf dari ke , kemudian memberikan warna pada titik-titik dari graf dualnya dengan menentukan bilangan kromatiknya. Diperoleh hasil bahwa Graf roda merupakan graf self-dual karena isomorfik dengan graf dualnya yaitu . Pewarnaan titik diperoleh dengan menentukan bilangan kromatik graf dual dari graf roda, menentukan pola dari bilangan kromatik, dan memberikan warna. Berdasarkan hasil penelitian, diperoleh bilangan kromatik pewarnaan titik pada graf dual dari graf roda yakni

Kata Kunci: Pewarnaan Titik, Bilangan Kromatik, Graf Dual dan Graf Roda.

This research aims to construct a dual graph from a wheel graph (W_n*) and determine the dual graph chromatic number of the wheel graph (W_n*). This research starts from describing some wheel graph from to , then construct a dual graph from a wheel graph from to , then gives color to the vertices of the dual graph by determining the chromatic number. The result showed that the wheel graph is a self-dual graph because it is isomorphic with its dual graph, namely . The vertex coloring is obtained by determining the chromatic number of the dual graph of the wheel graph, determining the pattern of the chromatic number and giving the color. Based on the research results, the chromatic number of vertex coloring on dual graph of a wheel graph is:

Keywords: Vertex Coloring, Chromatic Number, Dual Graph and Wheel Graph.

Full Text:

PDF

References

Abdussakir. (2009). Teori Graf. Malang: UIN Malang Press.

Assadillah, M. H. (2009). Dari Graf Roda (W_n) dan Graf Gear (G_n) (Skripsi). Universitas Islam Negeri, Malang.

Dewi, F. K. S. (2010). Pembangun Perangkat Lunak Pembangkit Jadwal Kuliah dan Ujian dengan Metode Pewarnaan Graf. Jurnal Buana Informatika, 1(1), 57-68.

Hasanah, U. (2012). Modifikasi Algoritma Welch-Powell untuk Pewarnaan Graf (Vertex Colouring) pada Penjadwalan Kuliah Jurusan Matematika Fakultas Sains Dan Teknologi UIN Suska Riau (Skripsi). Universitas Islam Negeri Sultan Syarif Kasim Riau, Pekan Baru.

Mahardika, F., & Marcos, H. (2017). Penerapan Algoritma Graf Welch Powel pada Penjadwalan Mata Kuliah dan Jadwal Asisten Study Kasus Forum Asisten Stmik Amikom Purwokerto. Jurnal Simetris, 8 (2). 825-832.

Muhib. (2013). Bilangan Kromatik Pewarnaan Titik pada Graf Dual dari Graf Piramida (Prn*) (Skripsi). Universitas Islma Negeri Maulana Malik Ibrahim, Malang.

Puspasari, D. S., & Dafik. (2014). Pewarnaan Titik pada Graf Khusus: Operasi dan Aplikasinya. Prosiding Seminar Nasional Matematika, 1(1), 50-58.

Setiawan, I. 2012. Pewarnaan Graf dan Aplikasinya (Skripsi). Universitas Negeri Makassar, Makassar.

Supriyandi & Eka, M. (2018). Penerapan Teknik Pewarnaan Graph pada Penjadwalan Ujian dengan Algoritma Welch-Powell. Jurnal Ilmu Komputer dan Informatika, 3(1), 58-63.

Welyyanti, D. (2018). Beberapa Syarat Cukup untuk Bilangan Kromatik Lokasi Hingga pada Graf Tak Terhubung. Jurnal Eksakta, 19(1), 76-82.