Article Per Year (5 Year)
p-Index From 2021 - 2026
0
P-Index
This Author published in this journals
All Journal Jurnal Matematika UNAND
Elza Zuriawan
Unknown Affiliation
Computer Science & IT Mathematics

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
HIMPUNAN PEWARNAAN PADA GRAF SEMPURNA Elza Zuriawan
Jurnal Matematika UNAND Vol 1, No 2 (2012)
Publisher : Jurusan Matematika FMIPA Universitas Andalas Padang

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.25077/jmu.1.2.1-4.2012

Abstract

Untuk suatu graf terhubung nontrivial G, c : V (G) ! N adalah suatupewarnaan titik di G, yang mana titik-titik yang saling bertetangga dapat diwarnaidengan warna yang sama. Untuk suatu titik v 2 V (G), himpunan warna lingkunganNC(v) adalah himpunan yang berisikan warna dari lingkungan v. Pewarnaan c dise-but suatu himpunan pewarnaan jika NC(u) 6= NC(v) untuk setiap pasangan titik u; vyang bertetangga di G. Bilangan minimum dari warna-warna yang dibutuhkan dari su-atu pewarnaan c disebut bilangan kromatik himpunan s(G). Pada makalah ini akandikaji kembali bahwa setiap graf k-colorability himpunan merupakan suatu masalah NP-complete dengan suatu transformasi kedalam k-colorability, sehingga bilangan kromatikhimpunan s dapat ditentukan dalam waktu polinomial. Dari ketiga kelas graf sempurnayang digunakan dalam tulisan ini, yaitu graf chordal, graf split, dan graf threshold, hanyagraf threshold yang bilangan kromatiknya bernilai sama dengan bilangan kromatik him-punannya. Selanjutnya pada tulisan ini juga telah ditunjukkan bahwa, jika G adalahgraf threshold, maka bilangan kromatik himpunan s(G) dapat dihitung secara esiendalam waktu polinomial.
Co-Authors