PEWARNAAN GRAF: POLINOMIAL KROMATIKDAN TEOREMA INVERSI MOBIUS

Abstract

Misalkan G graf sederhana, dan P(G; k)
menyatakan banyaknya cara mewarnai titik-titik di
G dengan k warna sedemikian hingga tidak ada dua
titik yang berhubungan langsung mendapat warna
sama. P(G;k) disebut polinomial kromatik dari G.
Untuk graf kincir
dan graf terpisah,
polinomial kromatiknya bisa ditentukan dengan
memeriksa struktur grafnya. Hubungan antara poset
dan graf dapat membantu menentukan polinomial
kromatik sebuah graf dengan memanfaatkan partisi
himpunan titik, latis ikatan dan teorema khusus
disebut Teorema Inversi Mobius.
Kata kunci: Polinomial kromatik, poset, latis
ikatan, Inversi Mobius.