Electronic Theses and Dissertation

Penelitian ini membahas mengenai konsep pewamaan graf tak lengkap pada verteks-verteksnya yaitu graf yang terdiri dari i, 2, 3, 4 dan 5 verteks, dengan graf dibentuk berdasakan jumlah derajat masing-masing verteks. pewamaan verteks menggunakan algoritrna welch powell dan diwarnakan maksimal dengan 4 warna. pewarnaan verteks merupakan pemberian warna atau label pada setiap verteks sehingga tidak ada 2 verteks bertetangga yang memiliki wama sama, dengan urutan pewarnaan verteks dari sebuah graf adalah merah, biru, kuning dan hijau. jumlah warna minimum yang dibutuhkan untuk mewarnai graf disebut bilangan kromatik. pewamaan verteks pada graf yang terdiri dari 1, 2, 3, 4 dan 5 verteks hanya membutuhkan 4 warna yang berbeda kecuali graf lengkap. bilangan kromatik suatu graf tak lengkap sama dengan bilangan kromatik subgraf dari graf tak lengkap tersebut dimana subgrafnya adalah sebuah graf lengkap. kata kunci : pewarnaan verteks, algoritma welch powell dan bilangan kromatik.