Analisis b-Coloring pada Keluarga Graf Tangga

Abstract

Pewarnaan graf merupakan salah satu topik penting dalam teori graf yang banyak dikaji karena aplikasinya digunakan dalam berbagai bidang. Salah satu pengembangan dari pewarnaan titik adalah b-coloring, yaitu pewarnaan graf yang selain memenuhi syarat pewarnaan biasa, juga mensyaratkan setiap warna memiliki minimal satu titik yang bertetangga pada setiap kelas warna lainnya. Penelitian ini bertujuan untuk menganalisis b-coloring pada keluarga graf tangga, yang meliputi Graf Tangga Segitiga Variasi, Graf Tangga Segitiga Melingkar, Graf Tangga Melingkar, Graf Tangga Mobius, Graf Tangga Miring, dan Graf Tangga Segitiga Liontin. Analisis dilakukan dengan menentukan pola pewarnaan, mengidentifikasi kelas warna, mengecek terpenuhinya definisi b-coloring, serta merumuskan dan membuktikan teorema bilangan b-chromatic 𝜑(𝐺) pada masing-masing graf. Penelitian ini menghasilkan enam teorema baru bilangan b-chromatic dari jenis graf tangga yang diteliti.