Perpustakaan Digital ITB

Bilangan Ramsey R(G,H) untuk suatu graf G dan H adalah bilangan bulat terkecil n sedemikian sehingga untuk sebarang graf F dengan n titik memenuhi sifat: F memuat G atau komplemen dari F memuat H. Batas bawah bilangan Ramsey R(G,H) yang diberikan oleh Chv¶atal dan Harary adalah R(G,H) > (X(H)-1)(C(G)-1) + 1, dengan X(H) adalah bilangan kromatik graf H dan C(G) adalah banyaknya titik pada komponen terbesar graf G. Sejak adanya batas bawah ini, kajian bilangan Ramsey berkembang pesat. Salah satu topik yang paling banyak dikaji adalah bilangan Ramsey untuk graf pohon. Hal ini disebabkan oleh struktur pohon yang berbeda-beda. Struktur yang paling sederhana adalah lintasan dan bintang. Karena itu, pengkajian bilangan Ramsey untuk graf pohon umumnya dimulai dengan pengkajian bilangan Ramsey untuk lintasan atau bintang.