Page 107 - Trends in Science and Technology fo Sustainable Living

68 Fakultas Sains dan Teknologi
Universitas Terbuka (2023)

Pada tahun 2011, Schiermeyer memperbaiki batas bawah
rc(G) pada Pertidaksamaan (1) dalam bentuk Teorema 1 berikut.
Untuk graf G berorde n, misalkan n(G) menyatakan banyaknya titik
i
G yang berderajat i untuk i ∈   1,n − 1  .

Teorema 1. (Schiermeyer, 2011)
Misalkan G graf terhubung dengan n ≥ 3 titik, maka
rc ( )G ≥ max{diam( ), ( )}G n G .
1
Selanjutnya perhatikan kembali graf Petersen pada Gambar
18. Karena bilangan terhubung pelangi graf Petersen adalah
rc(G) = 3, maka src(G)≥3. Akan tetapi pewarnaan-3 pelangi pada
Gambar 18 bukan pewarnaan-3 pelangi kuat, karena terdapat
geodesik x - y di graf Petersen yang bukan merupakan geodesik
x - y pelangi. Dalam hal ini, karena setiap pewarnaan pelangi kuat
dari graf Petersen G memetakan warna yang berbeda ke sisi yang
bertetangga, pewarnaan tersebut menjadi pewarnaan sisi murni.
Karena indeks kromatik dari graf Petersen adalah 4, diperoleh
src(G)≥4. Karena pewarnaan sisi graf Petersen seperti yang
ditunjukkan pada Gambar 19 berikut adalah pewarnaan-4 pelangi
kuat, maka src(G) = 4.

(a) (b)

Gambar 19. Pewarnaan-4 Pelangi Kuat Graf Petersen G (a) dengan
Label Angka (Chartrand & Zhang, 2020), (b) dengan Warna