PEWARNAAN TOTAL PADA GRAF RAJA

Abstract

Pewarnaan total graf merupakan pewarnaan sisi dan simpul sehingga tidak terdapat dua sisi dan dua simpul yang saling bertetangga serta setiap sisi dan simpul saling bersisian memiliki warna yang sama. Pada pewarnaan total graf berlaku dengan adalah derajat maksimum graf dan adalah jumlah minimum warna yang diperlukan dalam pewarnaan total. Tujuan pewarnaan total adalah untuk menentukan jumlah warna minimum yang dapat digunakan untuk mewarnai setiap sisi dan simpul pada graf. Penelitian ini membahas tentang algoritma pewarnaan total serta pengaruh sisi dan simpul terhadap bilangan kromatik pada graf raja. Algoritma pewarnaan total pada graf raja meliputi pembentukan graf raja, penentuan himpunan bebas sisi dengan syarat gabungan semua himpunan bebas sisi sama dengan himpunan sisi, pemberian warna pada sisi berdasarkan himpunan bebas sisi, pemberian warna pada simpul dan penentuan bilangan kromatik berdasarkan pada kaidah pewarnaan total. Graf raja dilambangkan dengan dengan adalah banyaknya baris dan adalah banyaknya kolom pada papan catur. Berdasarkan penelitian ini diperoleh bahwa bilangan kromatik pada graf raja yaitu untuk dan untuk dan , bilangan kromatik pada graf raja yaitu untuk dan untuk dan , bilangan kromatik pada graf raja yaitu untuk dan untuk , bilangan kromatik pada graf raja yaitu untuk dan bilangan kromatik pada graf raja yaitu untuk . Selain itu juga diperoleh bahwa sisi dan simpul sangat berpengaruh terhadap bilangan kromatik pewarnaan total pada graf raja.

Kata Kunci : bilangan kromatik, derajat maksimum, algoritma.