Perpustakaan Digital ITB

Misalkan G adalah graf terhubung tak trivial yang berhingga dan k 2 N. Misalkan pula T adalah suatu pohon pada G dan S V (G) adalah sub himpunan-k. T disebut pohon-S apabila setiap anggota S berada pada T. Kumpulan fT1; T2; Tlg dari pohon-S pada G dengan V (Ti) V (Tj) = S untuk setiap pasang i dan j, dengan i dan j di [1;] disebut himpunan pohon-S yang lepas secara internal. Definisikan suatu pewarnaan-t c : E(G) ! f1; 2; tg, t 2 N pada sisi-sisi graf G dengan dua buah sisi yang bertetangga dapat memiliki warna yang sama. T dikatakan sebagai pohon pelangi apabila setiap sisi pada T memiliki warna yang berbeda. Pewarnaan-t c yang setiap subhimpunan-k-nya memiliki ` buah pohon-S pelangi yang saling lepas secara internal disebut pewarnaan-t pelangi-(k;). Indeks Pelangi-(k;) pada G, dinotasikan rxk;(G), adalah bilangan t terkecil sehingga G memiliki pewarnaan-t pelangi-(k;)