Polinomial Kromatik Graf Lengkap Tripartit

Abstract

Polinomial kromatik pertama kali diperkenalkan oleh Birkhof pada tahun 1912, dan dilanjutkan oleh Whitney pada tahun 1932. Terinspirasi dari dugaan empat warna, pada tahun 1946 Birkhof dan Lewis mendapatkan polinomial kromatik dari graf planar dan membuat dugaan kuat mengenai teorema empat warna (TEW). Kajian mengenai polinomial kromatik telah dibahas oleh beberapa peneliti sebelumnya. Pada tahun 2004, Kurniawati telah melakukan penelitian mengenai polinomial kromatik dari graf lengkap, graf cycle, dan graf lintasan. Pada tahun 2007, Phoy telah melakukan penelitian mengenai polinomial kromatik dari graf bipartit dengan menghapus tiga dan empat sisi. Pada tahun 2009, Niswah telah melakukan penelitian mengenai pembuktian teorema polinomial kromatik dalam sudoku. Pada tahun 2011, Dwijayanti telah melakukan penelitian mengenai polinomial kromatik dari graf bintang, graf roda, dan graf tangga. Polinomial kromatik dinotasikan dengan 𝑃𝐺 (𝑡) adalah banyaknya cara untuk mewarnai titik-titik pada graf 𝐺 dengan 𝑡 warna (Wilson, 2010). Minimal warna yang diperlukan untuk mewarnai graf 𝐺 adalah sejumlah bilangan kromatiknya. Jika banyaknya warna yang dipakai untuk mewarnai graf 𝐺 kurang dari bilangan kromatiknya, maka 𝑃𝐺 (𝑡) = 0. Bilangan kromatik dinotasikan dengan 𝜒(𝐺) adalah banyak warna minimum yang digunakan untuk mewarnai titik-titik pada graf 𝐺 (Hartsfield dan Ringel, 1994). Graf 𝐺 dikatakan berkromatik-𝑡 jika 𝐺 terwarnai-𝑡 tetapi tidak terwarnai 𝑡 − 1, jika bilangan kromatik 𝐺 adalah 𝑡 maka dapat dituliskan dengan 𝜒(𝐺) = 𝑡. Pewarnaan titik pada graf adalah pemberian warna yang berbeda pada setiap titik sehingga tidak ada dua titik yang bertetangga dengan warna yang sama (Chartrand dan Zhang, 2009). Secara matematis, pewarnaan titik pada graf 𝐺 adalah fungsi 𝑐 ∶ 𝑉(𝐺) → 𝑍, dengan 𝑍 adalah himpunan warna, viii sedemikian sehingga 𝑐(𝑢) ≠ 𝑐(𝑣) jika 𝑢 dan 𝑣 merupakan dua titik yang bertetangga. Penelitian ini membahas mengenai polinomial kromatik dari graf lengkap tripartit 𝐾𝑙,𝑚,𝑛 dengan 𝑙, 𝑚 ∈ {1,2} dan 𝑙 ≤ 𝑚 ≤ 𝑛. Graf lengkap tripartit adalah sebuah graf lengkap 𝑘-partit dengan 𝑘 = 3 atau graf lengkap dengan 3 buah partisi himpunan titik. Misalkan 3 buah partisi himpunan titiknya adalah 𝑙, 𝑚, dan 𝑛 maka graf lengkap tripartit dinotasikan dengan 𝐾𝑙,𝑚,𝑛. Dalam hal ini, titik-titik pada setiap partisi saling bertetangga tetapi titik-titik pada sebuah partisi tidak saling bertetangga. Dari hasil penelitian, didapatkan polinomial kromatik dari graf 𝐾1,1,𝑛 yaitu 𝑃𝐾1,1,𝑛 (𝑡) = 𝑡(𝑡 − 1)(𝑡 − 2)𝑛, dari graf 𝐾1,2,𝑛 yaitu 𝑃𝐾1,2,𝑛 (𝑡) = 𝑡(𝑡 − 1)(𝑡 − 2)[(𝑡 − 3)𝑛 + (𝑡 − 2)𝑛−1], dan dari graf 𝐾2,2,𝑛 yaitu 𝑃𝐾2,2,𝑛 (𝑡) = 𝑡(𝑡 − 1)(𝑡 − 2)[(𝑡 − 3)2(𝑡 − 4)𝑛−1 + (𝑡 − 2)𝑛 − (𝑛2 − 3𝑛 + 2)(𝑡 − 3)𝑛−2].