Bilangan Kromatik Jarak-2 pada Beberapa Kelas Graf

Abstract

Pewarnaan graf merupakan salah satu kajian dalam teori graf yang bertujuan memberikan warna pada titik-titik graf dengan aturan tertentu. Salah satu pengembangannya adalah pewarnaan jarak-2, yaitu pewarnaan titik-titik graf sehingga setiap dua titik yang berjarak paling jauh dua memiliki warna yang berbeda. Penelitian ini bertujuan untuk menentukan nilai eksak bilangan kromatik jarak-2 pada beberapa kelas graf, yaitu graf sikel , graf bipartit komplet , graf komplet , graf bayangan , dan graf sentral. Penelitian ini merupakan penelitian teoritis dengan pendekatan deduktif. Hasil penelitian menunjukkan bahwa bilangan kromatik jarak-2 pada graf sikel bergantung pada nilai modulo tiga dari banyak titik, pada graf bipartit komplet sebesar jumlah titik pada kedua partisinya, dan pada graf komplet sebesar banyak titiknya. Selain itu, diperoleh hasil untuk graf bayangan dan graf sentral, dengan bilangan kromatik jarak-2 pada graf sentral dari graf komplet sebesar Disimpulkan bahwa struktur graf sangat mempengaruhi nilai bilangan kromatik jarak-2. Penelitian selanjutnya disarankan untuk mengkaji kelas graf lainnya.

Kata Kunci: pewarnaan graf, pewarnaan jarak-2, bilangan kromatik, graf bayangan dan graf sentral