GRAF PERFECT DAN GRAF IMPERFECT PADA BEBERAPA GRAF

Fransiskus Fran, Zakiah, Helmi,

BIMASTER
Vol 8, No 1 (2019): BIMASTER

Graf perfect adalah suatu graf G dengan setiap  subgraf induksi dari G memenuhi ?(H)=?(H), sedangkan jika terdapat H sehingga ?(H)>?(H) maka G disebut graf imperfect. Terdapat beberapa graf yang pada kondisi tertentu merupakan graf perfect dan pada kondisi yang lain merupakan graf imperfect. Pada tulisan ini dibahas tentang graf perfect dan graf imperfect pada beberapa graf yaitu graf sikel (Cn), graf roda (Wn), dan graf helm (Hn). Untuk C3,C2n, n?2, W3,W2n, n?2, H3, H2n, n?2 merupakan graf perfect, sedangkan untuk C(2n+1), n?2, W(2n+1) ,n?2, dan  H(2n+1) ,n?2 merupakan graf imperfect. Kata Kunci : subgraf induksi, pewarnaan graf, bilangan clique, bilangan kromatik