BILANGAN B-KROMATIK PADA GRAF ORIGAMI, GRAF LINTANG, DAN GRAF TADPOLE

Abstract

Pewarnaan -colouring pada graf  adalah pewarnaan simpul-simpul , sedemikian sehingga terdapat minimal satu simpul pada setiap kelas warna bertetangga dengan setidaknya satu simpul pada setiap kelas warna lainnya. Jumlah warna maksimum yang digunakan pada pewarnaan -colouring di graf  disebut dengan bilangan -kromatik yang dinotasikan dengan . Pada penelitian ini dibahas tentang bilangan -kromatik pada graf origami, graf lintang, dan graf tadpole. Graf origami (dinotasikan dengan On) merupakan graf dengan pusat berupa cycle dengan n  simpul dan lipatan-lipatan yang dibentuk dari penggabungan dua buah cycle C3   , sedangkan graf lintang (dinotasikan dengan Lm   ) terbentuk dari 2 simpul kutub dan m  simpul lintang, dan graf tadpole (dinotasikan dengan Tm,n) terbentuk dari graf lintasan dengan n  simpul dan graf cycle dengan m  simpul. Berdasarkan penelitian diperoleh bilangan -kromatik pada graf origami yaitu 4 untuk n  = 3 dan n  = 4, 5 untuk n  = 5, dan 6 untuk  â‰¥ 6. Bilangan b-kromatik pada graf lintang yaitu 2 untuk m  â‰¥ 2 dan bilangan -kromatik pada graf tadpole yaitu 3 untuk m  â‰¥ 3 dan n  â‰¥ 2.  

Kata Kunci: -colouring, graf origami, graf lintang, graf tadpole