PEWARNAAN JOHAN PADA GRAF DOUBLE WHEEL DAN DOUBLE GEAR - Diki Ipan (FMIPA Universitas Tanjungpura, 2023)
Suatu graf dapat diwarnai dengan pewarnaan Johan jika dan hanya jika untuk setiap simpul terdapat persekitaran pelangi pada graf dengan pewarnaan simpul (proper coloring) maksimum.. Persekitaran pelangi untuk graf adalah persekitaran tertutup yang memuat setidaknya satu simpul dari kelas warna. Misalkan adalah himpunan simpul-simpul yang diberi warna dengan disebut kelas warna, dimana adalah himpunan yang terdiri dari kelas warna dari . Tidak semua graf dapat diwarnai dengan pewarnaan Johan, graf yang dapat diwarnai dengan pewarnaan Johan adalah graf yang mencakup cycle yaitu graf double wheel dan double gear. Graf double wheel yang berukuran yang terdiri dari dua cycle dimana simpul pada dua cycle terhubung langsung dengan simpul utama dan graf double gear dapat diperoleh dari graf double wheel dengan cara menambahkan simpul pada setiap pasangan simpul di . Oleh karena itu penelitian ini membahas tentang pewarnaan Johan pada graf double wheel dan graf double gear . Maksimum banyaknya warna yang dapat diwarnai dengan pewarnaan Johan disebut -kromatik dilambang dengan . Penelitian ini dimulai dengan menerapkan pewarnaan simpul untuk graf double wheel dan double gear. Selanjutnya menentukan kelas warna dan persekitaran tertutup kemudian dapat diketahui persekitaran pelangi untuk setiap simpul pada graf double wheel dan double gear. Dengan demikian untuk setiap simpul pada graf double wheel dan double gear memiliki persekitaran pelangi dengan jumlah maksimum warna yang digunakan. Oleh karena itu graf double wheel dan double gear dapat dikatakan pewarnaan Johan. Berdasarkan hasil penelitian diperoleh jumlah maksimum warna yang dapat diwarnai dengan pewarnaan Johan untuk graf double wheel adalah , untuk dan untuk , tetapi . Jumlah maksimum warna yang dapat diwarnai dengan perwarnaan Johan pada graf double gear adalah untuk genap dan untuk ganjil. Kata Kunci: persekitaran tertutup, persekitaran pelangi, kelas warna