GRAF RAMSEY (3K2, 2P4) - MINIMAL
Diberikan graf G dan H. Notasi F → (G, H) berarti bahwa pada sebarang pewarnaan merah-biru terhadap sisi-sisi graf F, terdapat subgraf G yang memuat semua sisinya merah, atau subgraf H yang memuat semua sisinya biru. Kemudian notasi F ∗ 9 (G, H) berarti bahwa terdapat pewarnaan merah-biru terhadap s...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Department of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Andalas
2019-07-01
|
| Series: | Jurnal Matematika UNAND |
| Online Access: | https://jmua.fmipa.unand.ac.id/index.php/jmua/article/view/441 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Diberikan graf G dan H. Notasi F → (G, H) berarti bahwa pada sebarang pewarnaan merah-biru terhadap sisi-sisi graf F, terdapat subgraf G yang memuat semua sisinya merah, atau subgraf H yang memuat semua sisinya biru. Kemudian notasi F ∗ 9 (G, H) berarti bahwa terdapat pewarnaan merah-biru terhadap sisi-sisi graf F ∗, sedemikian sehingga tidak terdapat subgraf G yang semua sisinya merah dan subgraf H yang semua sisinya biru. Graf F dikatakan sebagai graf Ramsey (G, H) − minimal jika, (1) F → (G, H), (2) F ∗ 9 (G, H) dimana F ∗ := F − {e}, untuk setiap e ∈ E(F). Pewarnaan merah-biru yang tidak memuat subgraf merah G dan subgraf biru H didefinisikan sebagai pewarnaan − (G, H). Kelas yang memuat semua graf Ramsey (G, H)-minimal ditulis dengan R(G, H). Pada makalah ini akan diberikan syarat perlu untuk suatu graf yang menjadi anggota R(3K2, 2H) dengan H graf terhubung sebarang, dan mentukan graf yang menjadi anggota dari graf Ramsey (3K2, 2P4)−minimal.
Diterima: Direvisi: Dipublikasikan :
Kata Kunci: Graf Ramsey Minimal, Pewarnaan, 3K2 |
|---|---|
| ISSN: | 2303-291X 2721-9410 |