Perpustakaan Digital ITB

Bilangan Ramsey graf merupakan salah satu topik permasalahan yang berkembang dalam teori Ramsey. Misalkan F;G dan H adalah graf tak kosong. Notasi F → (G,H) menyatakan bahwa untuk setiap pewarnaan merah-biru dari pada semua sisi graf F akan mengakibatkan F memuat subgraf G yang berwarna merah atau F memuat subgraf H yang berwarna biru. Bilangan Ramsey r(G,H) adalah banyaknya titik minimum dari suatu graf F yang bersifat F →(G,H). Bilangan Ramsey untuk untuk graf lingkaran dan graf lengkap r(Cm;Kn) adalah bilangan bulat terkecil N dimana setiap graf G dengan N titik memiliki subgraf yang isomorfik dengan graf lingkaran Cm dengan m titik atau memiliki bilangan independen α(G) ≥ n. Penentuan bilangan Ramsey untuk graf lingkaran dan graf lengkap telah dipaparkan oleh Erdos, Faudree, Rousseau dan Schelp dalam konjektur yang menyatakan bahwa r(Cm,Kn) = (m-1)(n-1)+1 untuk setiap m ≥ n ≥ 3 kecuali r(C3,K3) = 6. Dalam tesis ini akan dibuktikan bahwa bilangan Ramsey untuk graf lingkaran dan graf lengkap r(C5,K9) = 33.