| dc.description.abstract | Teori graf banyak mengalami perkembangan yang sangat luas. Salah satu
topik yang menarik untuk dikaji adalah masalah pewarnaan. Pewarnaan memi-
liki tiga macam, yaitu pewarnaan titik (vertex coloring), pewarnaan sisi (edge
coloring), dan pewarnaan wilayah (region coloring). Penggunaan warna yang
berbeda untuk mewarnai semua titik pada graf dimana setiap dua titik yang ter-
hubung diberi warna yang berbeda disebut pewarnaan titik. Dalam pewarnaan
titik, tidak hanya memberi warna tetapi juga menghasilkan banyaknya warna
minimum yang didapatkan biasanya disebut bilangan kromatik yang dinotasikan
dengan (G). Selain itu, dikenal juga fungsi pewarnaan yang ditentukan dari
keteraturan bilangan kromatik. Terdapat topik baru yang masih dalam ruang
lingkup pewarnaan titik yaitu r-Dynamic Vertex Coloring atau yang biasa dise-
but pewarnaan titik dinamis. r-Dynamic Vertex Coloring ini sifatnya juga hampir
mirip dengan pewarnaan titik. Pewarnaan titik dapat diterapkan pada graf yang
merupakan hasil operasi dari beberapa graf khusus. Adapun macam-macam pen-
goperasian graf yaitu operasi Joint (G + H), Crown Product (G ⊙ H), Tensor
Product (G ⊗ H), Cartesian Product (G H), Composition (G[F]), Shackle, dan
Amalgamation. Pada penelitian ini menggunakan metode penelitian eksploaratif
dan terapan. Penelitian eksploratif adalah jenis penelitian yang bertujuan meng-
gali hal-hal yang ingin diketahui oleh peneliti dan hasil penelitian dapat digunakan
sebagai dasar penelitian selanjutnya. Penelitian terapan (applied research) meru-
pakan penyelidikan yang hati-hati, sistematik dan terus-menerus terhadap suatu
masalah dengan tujuan untuk digunakan dengan segera untuk keperluan tertentu.
Penelitian ini bertujuan untuk mencari batas atas bilangan kromatik dan fungsi
pewarnaan titik pada graf yang dioperasikan serta menentukan pewarnaan titik
dinamis. Selain itu juga untuk mengetahui sifat komuatif dari operasi graf. Graf
viii
yang digunakan pada penelitian ini adalah graf roda (wheel), graf lintasan (path),
graf lingkaran (cycle), dan graf bintang (star). Pada penelitian ini menghasilkan
15 teorema dan 4 akibat dari teorema sebelumnya, antara lain:
1. Teorema 4.1.1 Misal G= (Wn + Pm)= (Pm + Wn). Untuk n ≥ 3 dan
m ≥ 2, bilangan kromatik dan pewarnaan titik dinamis G adalah
(G = (Wn + Pm) = 4(G = (Wn + Pm) =
(
5, untuk n genap
6, untuk n ganjil
2. Teorema 4.1.2 Misal G adalah joint dari graf roda dan graf lingkaran.
Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik dan pewarnaan titik dinamis
G = (Wn + Cm) adalah
(Wn + Cm) = 4(Wn + Cm) =
(
5, untuk n genap pada saat m genap
6, untuk n ganjil pada saat m genap
(Wn + Cm) = 5(Wn + Cm) =
(
6, untuk n genap pada saat m ganjil
7, untuk n ganjil pada saat m ganjil
3. Teorema 4.1.3 Misal G adalah crown product dari graf roda dan graf lin-
tasan. Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan pewarnaan titik
dinamis G adalah
(Wn ⊙ Pm) = 2(Wn ⊙ Pm) =
(
3, untuk n genap
4, untuk n ganjil
4. Teorema 4.1.4 Misal G adalah crown product dari graf lintasan dan graf
roda. Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan pewarnaan titik
dinamis G= (Pm ⊙Wn) adalah
(Pm ⊙Wn) = 3(Wn ⊙ Pm) =
(
4, untuk n genap
5, untuk n ganjil
ix
5. Teorema 4.1.5 Misal G adalah crown product dari graf roda dan graf
lingkaran. Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik dan pewarnaan
titik dinamis G = (Wn ⊙ Cm) adalah
(Wn ⊙ Cm) = 2(Wn ⊙ Cm) = 4, untuk m genap
(Wn ⊙ Cm) = 3(Wn ⊙ Cm) = 4, untuk m ganjil
6. Akibat 4.1.1 Misal G= (Wn⊗Pm)= (Pm⊗Wn). Untuk n ≥ 3 dan m ≥ 2,
bilangan kromatik G adalah
(Wn ⊗ Pm) = 2
7. Teorema 4.1.6 Misal G= (Wn⊗Pm)= (Pm⊗Wn) untuk n ≥ 3 dan m ≥ 2,
pewarnaan titik dinamis G adalah
2(Wn ⊗ Pm) = 3
8. Akibat 4.1.2 Misal G adalah tensor product dari graf roda dan graf lingkaran.
Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik G = (Wn ⊗ Cm) adalah
(Wn ⊗ Cm) =
(
2, untuk m genap
3, untuk m ganjil
9. Teorema 4.1.7 Misal G adalah tensor product dari graf roda dan graf
lingkaran. Untuk n ≥ 3 dan m ≥ 3, pewarnaan titik dinamis G = (Wn⊗Cm)
adalah
(Wn Cm) = 2, untuk m genap
2(Wn Cm) = 3, untuk m ganjil
10. Akibat 4.1.3 Misal G= (Wn Pm)= (Pm Wn). Untuk n ≥ 3 dan m ≥ 2,
x
bilangan kromatik G adalah
(Wn Pm) =
(
3, untuk n genap
4, untuk n ganjil
11. Teorema 4.1.8 Misal G adalah cartesian product dari graf roda dan lin-
tasan. Untuk n ≥ 3 dan m ≥ 2, pewarnaan titik dinamis G = (Wn Pm)
adalah
2(Wn Pm) = 3, untuk m genap
2(Wn Pm) = 4, untuk m ganjil
12. Akibat 4.1.4 Misal G adalah cartesian product dari graf roda dan graf
lingkaran. Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik dan pewarnaan
dinamis G = (Wn Cm) adalah
(Wn Cm) =
(
3, untuk m genap dan m ganjil pada saat n genap
4, untuk m genap dan m ganjil pada saat n ganjil
13. Teorema 4.1.9 Misal G adalah cartesian product dari graf roda dan lingkaran.
Untuk n ≥ 3 dan m ≥ 3, pewarnaan titik dinamis G = (Wn Cm) adalah
2(Wn Cm) = 3, untuk m genap dan m ganjil pada saat n genap
3(Wn Cm) = 4, untuk m genap dan m ganjil pada saat n ganjil
14. Teorema 4.1.10 Misal G= (Wn[Pm])= (Pm[Wn]). Untuk n ≥ 3 dan m ≥ 2,
bilangan kromatik dan pewarnaan titik dinamis G adalah
(Wn[Pm]) = 5(Wn[Pm]) = 6, untuk n genap
(Wn[Pm]) = 6(Wn[Pm]) = 8, untuk n ganjil
15. Teorema 4.1.11Misal G adalah composition dari graf roda dan graf lingkaran.
Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik dan pewarnaan titik dinamis G
xi
adalah
(Wn[Cm]) = 3(Wn[Cm]) = 9, untuk n genap pada saat m ganjil
(Wn[Cm]) = 5(Wn[Cm]) = 6, untuk n genap pada saat m genap
(Wn[Cm]) = 5(Wn[Cm]) = 8, untuk n ganjil pada saat m genap
(Wn[Cm]) = 7(Wn[Cm]) = 12, untuk n ganjil pada saat m ganjil
16. Teorema 4.1.12 Misal G adalah amalgamation dari hasil operasi joint graf
roda dan graf lintasan. Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan
pewarnaan titik dinamis G = (Amal(Wn + Pm, v = 1, r)) adalah
(Amal(Wn+Pm, v = 1, r)) = 4(Amal(Wn+Pm, v = 1, r))
(
5, untuk n genap
6, untuk n ganjil
17. Teorema 4.1.13 Misal G adalah amalgamation dari hasil operasi joint graf
bintang dan graf lintasan. Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan
pewarnaan dinamis G = (Amal(Sn + Pm, v = 1, r)) adalah
(Amal(Sn + Pm, v = 1, r)) = 3(Amal(Sn + Pm, v = 1, r)) = 4
18. Teorema 4.1.14 Misal G adalah shackle dari graf hasil operasi joint graf
bintang dan graf lintasan. Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan
pewarnaan dinamis G = (Shack(Sn + Pm, r)) adalah
(Shack(Sn + Pm, r)) = 3(Shack(Sn + Pm, r)) = 4
19. Teorema 4.1.15 Misal G adalah shackle dari graf hasil operasi joint graf
roda dan graf lingkaran. Untuk n ≥ 3 dan r ≥ 3, bilangan kromatik dan | en_US |
