GRAF PERFECT DAN GRAF IMPERFECT PADA BEBERAPA GRAF

Zakiah Zakiah, Helmi Helmi, Fransiskus Fran

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 (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


Full Text:

PDF


DOI: https://doi.org/10.26418/bbimst.v8i1.30505

Refbacks

  • There are currently no refbacks.