GRAF PERFECT DAN GRAF IMPERFECT PADA BEBERAPA GRAF

Abstract

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 (C_n), graf roda (W_n), dan graf helm (H_n). Untuk C₃,C_2n, n≥2, W₃,W_2n, n≥2, H₃, H_2n, 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