Segitiga Pelangi pada Pewarnaan-Sisi Graf

Abstract

Graf yang digunakan dalam skripsi ini adalah graf sederhana dan berhingga. Misalkan  adalah graf. Pewarnaan-sisi pada  adalah sebuah pemetaan , dimana  adalah himpunan bilangan asli. Dalam kasus pewarnaan-sisi ini setiap dua sisi yang terkait pada titik yang sama boleh mendapat warna yang sama. Subgraf  dari graf  dengan pewarnaan-sisi  disebut subgraf pelangi jika semua sisi  mempunyai warna berbeda. Skripsi ini focus pada graf yang memiliki subgraf berupa segitiga atau . Dalam skripsi ini diperoleh beberapa syarat cukup bagi suatu pewarnaan-sisi pada graf sedemikian hingga memuat segitiga pelangi. Misalkan  adalah sebuah graf dengan  titik,  sisi, dan adalah sebuah pewarnaan-sisi dari . Kita buktikan bahwa jika , maka  memuat segitiga pelangi. Kita juga buktikan bahwa jika , maka  memuat segitiga pelangi. Akhirnya, kita buktikan bahwa jika  ganjil dan  untuk setiap , maka  memuat segitiga pelangi.

Kata Kunci: Pewarnaan-sisi, segitiga pelangi, syarat cukup.