Analisis b-Coloring pada Keluarga Graf Pohon

Abstract

Graf pohon merupakan graf terhubung dan tidak memiliki sirkuit. Graf pohon yang digunakan dalam penelitian ini antara lain: graf sapu, graf kembang api, graf pohon pisang, graf kelabang, graf E, dan graf bintang ganda. Pewarnaan graf merupakan proses pemberian warna pada elemen-elemen graf dengan aturan bahwa elemen-elemen yang bertetangga tidak boleh memiliki warna yang sama dan jumlah warna yang digunakan harus seminimal mungkin. b Pewarnaan graf G merupakan pewarnaan titik-titik pada G sedemikian rupa sehingga setiap kelas warna memiliki paling sedikit satu titik yang bertetangga dengan semua kelas warna lainnya. Bilangan kromatik b dari graf G dilambangkan dengan φ(G), merupakan bilangan bulat terbesar k sehingga G memiliki pewarnaan b dengan k warna. Limit pewarnaan b graf G dengan derajat maksimum ∆(G) adalah sebagai berikut. χ(G)≤φ(G)≤∆(G)+1.χ(G) merupakan bilangan kromatik dari suatu graf G, di mana χ(G) merupakan nilai warna minimum yang diperlukan untuk pewarnaan graf G yang baik. Sedangkan ∆(G) merupakan derajat maksimum titik-titik pada graf G. Penelitian ini menggunakan jenis penelitian eksploratori dengan metode deduktif aksiomatik dan metode deteksi pola. Berdasarkan hasil penelitian ini, maka dapat diketahui hasil analisis pewarnaan b pada keluarga graf pohon. Hasil penelitian ini diharapkan dapat digunakan sebagai bahan kajian dan pengembangan ilmu pengetahuan terkait analisis pewarnaan b pada graf lainnya.