III. BILANGAN KROMATIK LOKASI GRAF

Bilangan kromatik lokasi graf pertama kali dikaji oleh Chartrand dkk. (2002). Konsep

ini merupakan pengembangan dari konsep dimensi partisi dan pewarnaan graf.

Pewarnaan titik pada graf adalah : ( ) → {1,2,3, … , } dengan syarat untuk setiap

dua titik yang bertetangga harus memiliki warna yang berbeda. Minimum banyaknya

warna yang digunakan untuk pewarnaan titik pada graf disebut bilangan kromatik,

yang dinotasikan ( ).11

1

2

2

22

1v

2v3v

4v

5v

6v

7v

Gambar 15. Contoh bilangan kromatik dengan ( ) = 2Berikut ini diberikan definisi bilangan kromatik lokasi graf yang diambil dari

(Chartrand, dkk, 2002). Misalkan c suatu pewarnaan titik pada graf G dengan( ) ≠ ( ) untuk u dan yang bertetangga di G. Misalkan himpunan titik–titik

yang diberi warna i, yang selanjutnya disebut kelas warna, maka Π = { , , … , }

21

adalah himpunan yang terdiri dari kelas – kelas warna dari V(G). Kode warna ( )dari v adalah k-pasang terurut ( , ), ( , ), … , ( , ) dengan ( , ) =

min{ ( , )| ∈ } untuk 1 ≤ ≤ . Jika setiap G mempunyai kode warna yang

berbeda, maka c disebut pewarnaan lokasi G. Banyaknya warna minimum yang

digunakan untuk pewarnaan lokasi disebut bilangan kromatik lokasi dari G, dan

dinotasikan dengan ( ). Karena setiap pewarnaan lokasi juga merupakan

pewarnaan, maka ( ) ≤ ( ).Teorema 3.1 (Chartrand dkk, 2002) Misal adalah suatu pewarnaan lokasi pada

graf terhubung . Jika dan adalah dua titik pada graf sedemikian sehingga( , ) = ( , ) untuk setiap ∈ ( ) ∖ { , }, maka ( ) ≠ ( ). Dalam hal

khusus, jika dan adalah titik-titik yang tidak bertetangga di sedemikian

sehingga ( ) ≠ ( ) , maka ( ) ≠ ( ).Bukti: Misalkan adalah suatu pewarnaan lokasi pada graf terhubung dan

misalkan Π = { , , … , } adalah partisi dari titik-titik ke dalam kelas warna .

Untuk titik , ( ), andaikan ( ) = ( ) sedemikian sehingga titik dan

berada dalam kelas warna yang sama, misal dari Π. Akibatnya,( , ) = ( , )= 0. Karena ( , ) = ( , ) untuk setiap ∈ ( ) ∖ { , }maka ( , ) = ( , ) untuk setiap ≠ , 1 ≤ ≤ . Akibatnya, ( ) = ( )sehingga bukan pewarnaan lokasi. Jadi ( ) ≠ ( ). ■

22

Akibat 3.1 (Chartrand dkk, 2002) Jika adalah suatu graf terhubung yang memuat

suatu titik yang bertetangga dengan daun di , maka ( ) ≥ + 1.Bukti: Misalkan adalah suatu titik yang bertetangga dengan daun , , … , di

. Berdasarkan Teorema 3.1, setiap pewarnaan lokasi dari mempunyai pewarnaan

yang berbeda untuk setiap , = 1,2, … , . Karena bertetangga dengan semua ,

maka harus mempunyai warna yang berbeda dengan semua daun . Akibatnya( ) ≥ + 1. ■

3

2

2

14

1v

3v

4v

7v2v 2

15v

8v

9v

6v

13

Gambar 16. Contoh pewarnaan lokasi minimum pada Graf

Teorema 3.2 (Chartrand dkk, 2003) Misalkan adalah derajat maksimum di graf

maka ( ) ≤ + 1.Beberapa teorema penelitian sebelumnya yang mendukung penelitian ini adalah

sebagai berikut.

Teorema 3.3 (Chartrand dkk, 2002) Bilangan kromatik lokasi graf lintasan( ≥ 3) adalah 3.

23

Bukti: Perhatikan bahwa ( ) = 1 dan ( ) = 2 . Jelaslah bahwa ( ) ≥ 3untuk ≥ 3 . Berdasarkan Teorema 3.2. ( ) ≤ + 1, dengan derajat titik

maksimum. Karena pada , = 2 maka ( ) ≤ 2 + 1. Akibatnya ( ) ≤ 3.Jadi, ( ) ≤ 3. ■

1 1 1 12 2 23

1v 2v 4v3v 5v 6v 1nv nv

Gambar 17. Pewarnaan lokasi minimum pada graf lintasan

Teorema 3.4 (Chartrand dkk, 2002) Untuk bilangan bulat dan dengan1 ≤ ≤ dan ≥ 2, , = + 1 .

Bukti: Berdasarkan Akibat 3.1, diperoleh batas bawah yaitu , ≥ + 1.Selanjutnya, akan ditentukan batas atasnya, yaitu , ≤ + 1. Misalkan

adalah pewarnaan titik menggunakan ( + 1) warna sebagaimana terlihat pada

Gambar 18. Perhatikan bahwa kode warna dari setiap titik , berbeda, akibatnya

adalah pewarnaan lokasi.Jadi, , ≤ + 1. ■

24

1b

u v

1a

1

1

a

b

2 2

3

Gambar 18. Pewarnaan lokasi minimum pada Graf ,

Teorema 3.5 (Chartrand dkk, 2002) Terdapat pohon berorde ≥ 5 yang

mempunyai bilangan kromatik jika dan hanya jika ∈ {3, 4, … , − 2, }.1

1ku

2

k 12 2

2v 4v3v1v1knv

1

2u1u

1k

Gambar 19. Pohon T dari berorde dengan ( ) =Bukti: Pertama misalkan ∈ {3, 4, … , − 2, }. Untuk = 3, misalkan = ,

untuk = , misalkan = , . Sehingga diasumsikan bahwa 4 ≤ ≤ − 2.Misalkan didapat dari lintasan : , , … , dengan menambahkan( − 1) titik baru , , … , dan hubungkan setiap , untuk 1 ≤ ≤ − 1dengan . Berikanlah warna pada , warna 1 pada jika genap , warna 2

pada jika ≥ 3 dan ganjil, dan warna pada , untuk 1 ≤ ≤ − 1 lihat

Gambar 19. Dengan demikian ( ) adalah pewarnaan lokasi, ( ) ≤ .

25

berdasarkan akibat 3.1 ( ) ≥ maka ( ) = . ■

Lemma 3.2 (Asmiati dkk, 2011) Misalkan adalah pewarnaan lokasi dari ,menggunakan paling sedikit warna dengan , ≥ 2. Pewarnaan adalah

pewarnaan lokasi jika dan hanya ( ) = ( ), ≠ mengakibatkan( ) = 1,2,3, … , − 1 dan ( ) = 1,2,3, … , − 1 adalah dua himpunan

yang berbeda.

Bukti: Misalkan = ( ) = 1,2,3, … , − 1 dan = { ( ( ) =1,2,3, … , − 1}. Misalkan adalah pewarnaan lokasi dari , , ≥ 2, ≥ 2 dan( ) = ( ), untuk suatu ≠ . Andaikan = . Karena ( , ) = ( , ) untuk

setiap ∈ ∖ ( ) = 1,2,3, … , − 1 ∪ = ( ) = 1,2,3, … , − 1 ,

maka kode warna dari dan sama. Jadi bukan pewarnaan lokasi, suatu

kontradiksi. Akibatnya ≠ . Misalkan Π suatu partisi dari ( ) dari terhadap

kelas-kelas warna |Π| ≥ . Pandang ( ) = ( ), ≠ . Karena ≠ , maka

terdapat warna dan sedemikian sehingga ( ∈ , ∉ ) atau ( ∈ , ∉ ).

Selanjutnya akan ditunjukkan bahwa kode warna untuk setiap ∈ , . Jelas bahwa ( ) ≠ ( ), karena kedua kode warna tersebut berbeda pada

ordinat ke- atau ke- .

Jika ( ) ≠ ( ), untuk setiap ≠ , dibagi menjadi dua kasus.

26

Kasus 1: Jika ( ) = ( ), maka berdasarkan premis dari teorema ini, ≠ . Jadi( ) ≠ ( ).

Kasus 2: Misalkan ( ) = dan ( ) = , dengan ≠ . Maka ( ) ≠( ) karena kedua kode warna tersebut berbeda sekurang-kurangnya

pada ordinat yang ke- dan .

Jika ( ) = ( ), maka kode warna dari ( ) memuat sedikitnya dua

komponen yang bernilai 1. Akibatnya ( ) = ( ).

Berdasarkan semua kasus di atas, dapat dilihat bahwa kode warna untuk semua titik

di , berbeda, maka merupakan pewarnaaan lokasi. ■

Lemma 3.3 (Asmiati dkk, 2011) Misalkan adalah pewarnaan lokasi dari ,menggunakan + warna dan ( ) = ( + − 1) + − 1− 1 , ≥ 0, maka≤ ( ).

Bukti: Misal adalah pewarnaan lokasi dari , menggunakan + warna, Untuk

suatu titik tetap , misal ( ) warna dari titik tengah . maka banyak kombinasi

warna yang digunakan oleh = 1,2,3, … , − 1 adalah + − 1− 1 .

Karena satu warna digunakan untuk titik pusat amalgamasi , maka terdapat( + − 1) untuk , untuk setiap = 1,2,3, … , . Dari Lemma 3.2,

diperoleh nilai maksimum dari adalah ( ) = ( + − 1) + − 1− 1 , ≥ 0,

maka ≤ ( ). ■

27

Teorema 3.6 (Asmiati dkk, 2011) Jika ( ) = ( + − 1) + − 1− 1 untuk≥ 0, ≥ 2, dan ≥ 3, maka

, = ; 2 ≤ ≤ (0), ≥ 3+ ; ( − 1) < < ( ), ≥ 1Bukti: Pertama-tama akan dicari batas bawah dan batas atas dari , untuk2 ≤ ≤ (0) = − 1.

(1) Batas bawah dari , .

Berdasarkan Akibat 3.1, setiap titik bertetangga dengan ( − 1)daun, untuk

titik = 1,2,3, … , . Dengan demikian , ≥ .

(2) Batas atas dari ,Misalkan adalah pewarnaan dari , menggunakan warna. Tanpa

mengurangi keumuman , misal ( ) = 1 dan ( ) = + 1 untuk = 1,2,3, … , .

Karena daun-daun harus mempunyai kode warna yang berbeda, maka daun-daun= 1,2, … , − 1 diberi warna oleh {1,2, … , }\{ + 1} untuk sebarang .

Maka, berdasarkan Lemma 3.1, adalah pewarnaan lokasi. Dengan demikian

, ≤ .

Selanjutnya, akan dicari batas bawah dan batas atas untuk( − 1) < < ( ), ≥ 1 , yaitu sebagai berikut.

28

(1) Batas bawah dari ,Karena > ( − 1), maka berdasarkan Lemma 2.3, , ≥ + . Pada

sisi lain, jika > ( ) maka berdasarkan Lemma 3.3, ( , ) ≥ + + 1.Dengan demikian, , ≥ + jika ( − 1) < < ( ).

(2) Batas atas dari ,Karena ( ) = 1 dan warna dari titik tengah adalah 2,3, … , + . Karena( − 1) < < ( ), ≥ 1 maka banyak titik tengah yang mempunyai warna

yang sama tidak lebih dari + + 1− 1 , untuk sebarang . Akibatnya

jika ( ) = 1,2,3, … , − 1 ≠ ( ) = 1,2,3, … , − 1 . Berdasarkan

Lemma 3.3, adalah pewarnaan lokasi. Jadi, , ≤ + untuk( − 1) < < ( ). ■

31

2

4

5

11

11

2

2

2

3

3

3

4

4

4

5

5

5

6

6

6

6

Gambar 20. Pewarnaan lokasi minimum pada graf ,

29

3

2

4

1

1

1

2

22

1

1

1

1

2

2

3

3

3

4

2

33

4

44

4

3

Gambar 21. Pewarnaan lokasi minimum pada graf ,