Perpustakaan Digital ITB

Graf G adalah himpunan titik-titik tak hampa V(G) dan himpunan sisi E(G). bilangan ramsey r(m,n) adalah suatu bilangan bulat terkecil r sehingga untuk setiap pewarnaan merah-biru pada sisi-sisi graf komplit Kr dengan r titik selalu terdapat graf komplit Km merah atau graf komplit Kn biru sebagai suatu subgraf, untuk suatu bilangan bulat positif m,n. Untuk graf F, G dan H tertentu, notasi F -> (G,H) berarti bahwa pada setiap pewarnaan merahbiru pada sisi F, maka akan terdapat subgraf G merah atau subgraf H biru pada F. pewarnaan-(G,H) adalah 2-pewarnaan (pewarnaan merah-biru) sehingga tidak terdapat G merah maupun H biru. Graf F disebut Ramsey minimal-(G,H) jika untuk setiap pewarnaan merah-biru pada sisi F, maka terdapat subgraf G merah atau subgraf G biru pada F dan terdapat pewarnaan merah-biru pada F-{e}, untuk setiap sisi e di F, sehingga tidak muncul subgraf G merah maupun subgraf H biru. Selanjutnya, R(G,H) menyatakan kelas yang terdiri dari semua graf Ramsey minimal-(G,H). Pada tugas akhir ini penulis mengkaji kelas graf R(P3,H). Kami akan memberikan beberapa graf yang termasuk dalam himpunan ramsey minimal ini.