Semua graf yang dibahas dalam tesis ini merupakan graf sederhana, hingga, tak berarah, dan taktrivial. Misalkan r ∈ N, n ∈ N, dan G = (V (G),E(G)) merupakan graf terhubung-r berorde n. Fungsi c : E(G) [1,k] untuk suatu k ∈ N disebut sebagai pewarnaan sisi-k pelangi pada G, jika setiap pasang titik u dan v di V (G) terdapat lintasan u−v dengan setiap sisi pada lintasan tersebut memiliki warna berbeda. Lintasan u − v yang seperti itu disebut lintasan pelangi. Misalkan l ∈N dengan l ≤ r, c disebut pewarnaan-k pelangil, jika tiap sepasang titik di G memiliki l buah lintasan pelangi yang saling lepas secara internal. Graf G yang dikenakan pewarnaan-k pelangi-l disebut terhubung-l pelangi. Bilangan terhubung-l pelangi, dinotasikan sebagai rcl(G), merupakan banyaknya warna minimal yang dibutuhkan sehingga G bersifat terhubung-l pelangi.