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.