Perpustakaan Digital ITB

Permasalahan penentuan bilangan Ramsey multipartit-ukuran merupakan salah satu variasi dari penentuan bilangan Ramsey graf dengan menjadikan graf multipartit seimbang lengkap sebagai domainnya. Misalkan K_(j×t) merupakan sebuah graf multipartit seimbang lengkap yang memuat j himpunan partit dan t titik di setiap partitnya. Untuk graf sederhana G dan H, bilangan Ramsey multipartit-ukuran m_j (G,H) adalah bilangan asli terkecil t sedemikian sehingga pewarnaan sebarang merah-biru pada sisi-sisi graf K_(j×t) akan mengakibatkan graf K_(j×t) memuat graf merah G atau graf biru H sebagai subgraf. Gagasan tentang bilangan Ramsey multipartit untuk kombinasi graf multipartit seimbang lengkap telah diperkenalkan dan dipopulerkan oleh Burger dan Vuuren (2004). Konsep bilangan Ramsey multipartit-himpunan (Burger dan Vuuren, 2004a) dan konsep bilangan Ramsey multipartit-ukuran (Burger dan Vuuren, 2004b) diperkenalkan oleh mereka dalam dua artikel yang berbeda. Sifat-sifat dasar, batas bawah, dan batas atas untuk kedua bilangan Ramsey multipartit tersebut, beserta kaitan antara keduanya diberikan oleh Burger dan Vuuren. Beberapa bilangan Ramsey multipartit-himpunan dan ukuran untuk kombinasi dua graf multipartit seimbang lengkap berorde kecil juga ditunjukkan pada kedua artikel mereka. Pada tahun 2005, konsep bilangan Ramsey multipartit-ukuran diperumum oleh Syafrizal dkk. dengan menghilangkan syarat kelengkapan bagi subgraf yang dikandungnya. Dalam dua artikel yang berbeda (2005 dan 2009), mereka juga menentukan bilangan Ramsey multipartit untuk kombinasi graf-graf lintasan m_j (P_n,P_n ), dengan n?2. Lebih khusus, bilangan Ramsey tripartit untuk kombinasi graf-graf lintasan juga diberikan oleh Gy`arf`as dkk. (2007). Berikutnya, hasil untuk kombinasi graf lintasan versus graf lainnya seperti graf siklus, graf roda, graf bintang, graf kipas, graf cocktail party, graf multipartit seimbang lengkap maupun graf pohon telah ditentukan oleh Syafrizal dkk. (2007, 2011 dan 2012). Bilangan Ramsey tripartit untuk graf-graf pohon juga diberikan oleh B¨ottcher dkk. (2009). Lebih jauh, bilangan Ramsey multipartit-ukuran untuk kombinasi graf bintang versus graf lintasan diberikan oleh Surahmat dkk. (2014) dan Effendi dkk. (2016). Sementara itu, untuk kombinasi graf lintasan atau graf siklus versus graf buku, graf padanan, atau graf bintang diberikan oleh Jayawardene dkk. (2016–2017). Hasil-hasil penelitian tentang bilangan Ramsey multipartit untuk graf lengkap masih terbatas pada kombinasi graf lengkap berorde kecil. Sementara itu, untuk graf yang tidak harus lengkap, cukup banyak pada kombinasi graf lintasan versus graf lainnya, sedangkan kombinasi graf siklus, graf pohon, atau graf bintang versus graf lainnya masih sedikit. Dengan demikian, bilangan Ramsey multipatit untuk kombinasi graf bintang ataupun gabungan graf bintang masih menjadi masalah terbuka. Selain itu, masalah ini merupakan masalah yang menarik untuk dikaji, misalnya ketika mengkonstruksi gabungan saling lepas bintang-bintang dalam subgraf berwarna merah sedemikian sehingga dapat menghindari penggunaan sisi-sisi dalam subgraf berwarna biru. Penelitian disertasi ini difokuskan pada penentuan bilangan Ramsey multipartit ukuran m_j (G,H), dengan G adalah graf bintang atau gabungan saling lepas t buah graf bintang homogen tK_(1,n) atau graf bintang heterogen ?_(i=1)^t?K_(1,n_i ) , untuk n,t?1 dan graf H adalah graf lintasan, graf siklus, atau graf bintang. Penulisan hasil-hasil penelitian ini disajikan dalam dua bagian. Pertama, bilangan Ramsey multipartit-ukuran untuk kombinasi graf bintang versus graf siklus, graf lintasan, atau graf bintang. Kedua, bilangan Ramsey multipartit-ukuran untuk kombinasi gabungan graf bintang versus graf P_3,K_1.3, dan C_3. Selain itu, dihasilkan juga konsep mengenai eksistensi dan nilai asimptotik bilangan Ramsey multipartit untuk kombinasi graf yang tidak harus lengkap sebagai turunan konsep yang telah diberikan oleh Burger dan Vuuren. Hasil penelitian bagian pertama yaitu bilangan Ramsey multipartit pada kombinasi graf bintang versus graf siklus m_j (K_(1,r),C_n ), untuk semua n,j,r?2. Hasil lainnya adalah bilangan Ramsey tripartit pada kombinasi graf bintang versus graf lintasan m_3 (K_(1,r),P_n ), untuk n,r?2 dan bilangan Ramsey multipartit pada kombinasi dua graf bintang m_j (K_(1,r),K_(1,s) ); untuk j=2,3 dan r,s?1. Kemudian, hasil penelitian bagian kedua meliputi bilangan Ramsey multipartit pada kombinasi gabungan graf bintang versus graf berukuran maksimal 3 sisi. Bilangan Ramsey multipartit pada kombinasi gabungan graf bintang homogen versus P_3 atau K_1.3 diperoleh untuk semua parameter yang digunakan. Sementara itu, pada kombinasi gabungan graf bintang homogen versus C_3 diperoleh batas bawah bilangan Ramsey tripartit, karena sulitnya menjamin eksistensi tK_(1,n) merah ketika menghindari C_3 biru. Hasil terakhir pada bagian kedua adalah bilangan Ramsey multipartit pada kombinasi gabungan graf bintang heterogen versus P_3. Kasus gabungan dua hingga empat bintang heterogen telah berhasil dibuktikan, namun kasus gabungan t buah bintang heterogen masih merupakan masalah terbuka dan disajikan dalam sebuah konjektur.