Analisis B-Coloring pada Keluarga Graf Pohon

Abstract

Pewarnaan graf adalah 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. Suatu pewarnaan pada seluruh titik anggota graf 𝐺 = (𝑉, 𝐸) adalah pemetaan 𝐹: 𝑉 → ℕ dengan ketentuan titik-titik yang bertetangga memiliki warna-warna yang berbeda di ℕ, artinya {𝑣1, 𝑣2} ∈ 𝛦 maka 𝐹(𝑣1) ≠ 𝐹(𝑣2). Bilangan kromatik graf 𝐺 ialah minimum banyaknya warna yang digunakan dalam mewarnai titik-titk di 𝐺, sedemikian sehingga setiap dua titik yang berhubungan dengan satu sisi memiliki warna yang berbeda. Bilangan kromatik dari graf 𝐺 dilambangkan dengan 𝜒(𝐺). bcoloring dari sebuah graf 𝐺 adalah sebuah pewarnaan dari titik-titik 𝐺 sedemikian hingga setiap kelas warna memiliki setidaknya satu titik yang bertetangga dengan semua kelas warna lainnya. Tujuan penelitian ini adalah mengetahui analisis b-coloring pada keluarga graf pohon. Keluarga graf pohon adalah graf tak berarah, terhubung, dan tidak mengandung sirkuit. Graf pohon yang digunakan dalam penelitian ini adalah graf sapu, graf pohon pisang, graf centipede, graf E, graf kembang api, dan graf bintang ganda. Jenis penelitian ini termasuk penelitian eksploratif. Metode penelitian yang digunakan yaitu metode deduktif aksiomatik dan pendeteksian pola (pattern recognition). Metode deduktif aksiomatik adalah metode penelitian yang menggunakan prinsip-prinsip pembuktian deduktif yang berlaku dalam logika matematika dengan menggunakan aksioma, lemma atau teorema yang dapat diterapkan dalam analisis b-coloring pada keluarga graf pohon.