Perpustakaan Digital ITB

Misalkan c adalah sebuah pewarnaan titik dengan n warna pada graf terhubung G. Misalkan juga = fC1;C2; : : : ;Cng adalah partisi dari V (G) yang diinduksi dari c, dengan Ci adalah himpunan titik yang berwarna i, untuk 1 i n. Kode warna c(v) dari titik v adalah (d(v;C1); d(v;C2); : : : ; d(v;Cn)), dimana d(v;Ci) = minfd(v; x)jx 2 Cig, untuk 1 i n. Jika setiap dua titik berbeda u; v pada G memenuhi c(u) 6= c(v), maka c disebut pewarnaan lokasi dari G. Bilangan kromatik lokasi dari G, dinotasikan dengan L(G), adalah n terkecil sedemikian sehingga G mempunyai pewarnaan lokasi dengan n warna. Misalkan B(k) adalah pohon biner lengkap yang jarak antara akar dan daun adalah k. Pada tugas akhir ini, dikaji batas atas dan batas bawah bagi L(B(k)), untuk setiap k 6. Secara khusus, dibuktikan nilai eksak bagi L(B(k)) untuk k = 7 dan 8.