Analisis b-Coloring pada Graf Hasil Operasi Comb Graf Lintasan

Abstract

Misalkan 𝐺 adalah pasangan dua himpunan (𝑉, 𝐸) dengan himpunan titik 𝑉 dan himpunan sisi 𝐸. Pewarnaan yang tepat dari suatu graf 𝐺 adalah pewarnaan titik sedemikian sehingga tidak ada dua titik yang bertetangga memiliki warna yang sama. Salah satu contoh adalah b-Coloring merupakan pewarnaan graf yang mengharuskan setiap kelas warna memiliki setidaknya satu titik yang bertetangga dengan semua kelas warna lainnya. b-Chromatic number merupakan bilangan terbesar 𝑘 yang menunjukkan bahwa suatu graf memiliki b-coloring dengan 𝑘 warna dan dilambangkan dengan 𝜑(𝐺). Salah satu operasi graf yaitu operasi comb titik dinotasikan dengan 𝐺 ⊳𝑜 𝐻 adalah graf yang diperoleh melalui penggandaan graf 𝐻 sampai banyaknya graf 𝐻 sama dengan kardinalitas titik pada graf 𝐺. Penelitian ini bertujuan untuk mendapatkan b-chromatic number dari hasil b coloring pada graf hasil operasi comb graf lintasan yang menghasilkan tujuh teorema baru diantaranya graf 𝑃𝑛 ⊳𝑣3 𝑃𝑚, graf 𝑃𝑛 ⊳𝑣1 𝐶𝑚, graf 𝐶𝑛 ⊳𝑣1 𝑃𝑚, graf 𝑆𝐿𝑛 ⊳𝑣1 𝑃𝑚, graf 𝑃𝑇𝐿𝑛 ⊳𝑣1 𝑃𝑚, graf 𝐷𝐿𝑛 ⊳𝑣1 𝑃𝑚, dan graf 𝐿𝑆𝑃𝑛 ⊳𝑣1 𝑃𝑚