Strong Rainbow Cycle Forbidding pada Beberapa Graf dengan Girth n≥6

HARYADI, TRI IRVAN (2024) Strong Rainbow Cycle Forbidding pada Beberapa Graf dengan Girth n≥6. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 6002212003-Master_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (12MB) | Request a copy

Abstract

Di dalam konsep anti-Ramsey, maksimum banyak warna yang digunakan pada pewarnaan sisi menjadi objek utama penelitian sedemikian hingga tidak terdapat suatu klasifikasi subgraf yang pelangi (semua sisinya berbeda warna). Untuk kelas graf siklus, konsep ini dikembangkan dalam pewarnaan rainbow-cycle-forbidding/RCF. Pewarnaan tersebut tidak menghendaki adanya subgraf siklus pelangi di dalam suatu graf berapapun banyak warna yang digunakan. RCF yang menggunakan aturan pewarnaan sisi sejati kemudian disebut proper rainbow-cycle-forbidding/PRCF. Graf yang dapat dikenakan pewarnaan PRCF dapat disebut sebagai graf PRCF-good, dan jika tidak maka disebut graf PRCF-bad. Pengembangan lebih lanjut dari RCF dilakukan pada penelitian ini menggunakan aturan pewarnaan sisi kuat yang selanjutnya disebut pewarnaan strong rainbow-cycle-forbidding/SRCF. Analisis dilakukan pada graf-graf khusus, apakah dapat dikenakan pewarnaan SRCF atau tidak. Begitu pula untuk graf dengan girth n ≥ 6 dan graf hasil operasi. Hasilnya, beberapa graf khusus dapat dikategorikan sebagai graf SRCF-good sementara beberapa yang lain perlu kondisi khusus berkaitan dengan ordonya. Graf Heawood menjadi salah satu graf dengan girth enam yang merupakan graf SRCF-bad. Graf-graf umum dengan girth n ≤ 5 secara pasti tidak dapat dikenakan pewarnaan SRCF sehingga di dalam penelitian ini dikategorikan sebagai graf SRCF-bad.

============================================================

In the anti-Ramsey concept, the maximum number of colors used in edge coloring is the main object of research so that there is no subgraph classification that are rainbow (all edges are in different colors). For the cycle graph class, this concept was developed in rainbow-cycle-forbidding/RCF coloring. This coloring does not require the presence of rainbow cycle subgraphs in a graph regardless of how many colors are used. RCF that uses proper edge coloring rules is then called proper rainbow-cycle-forbidding/PRCF. Graphs that can be subjected to PRCF coloring can be called PRCF-good, and otherwise they are called PRCF-bad. Further development of RCF was carried out in this research using the strong edge coloring rule, hereinafter called strong rainbow-cycle-forbidding/SRCF coloring. Analysis is performed on special graphs, whether they can be subjected to SRCF staining or not. Likewise for graphs of girth n ≥ 6 and graphs resulting from operations. As a result, some special graphs can be categorized as SRCF-good while some others require special conditions regarding their order. The Heawood graph is one of the graphs with girth six that is SRCF-bad. General graphs with girth n ≤ 5 definitely cannot be subjected to SRCF coloring so in this study they are categorized as SRCF-bad graphs.

Item Type:	Thesis (Masters)
Uncontrolled Keywords:	girth, rainbow-cycle-forbidding, proper rainbow-cycle-forbidding, strong rainbow-cycle-forbidding
Subjects:	Q Science > QA Mathematics > QA159 Algebra Q Science > QA Mathematics > QA166 Graph theory
Divisions:	Faculty of Science and Data Analytics (SCIENTICS) > Mathematics > 44101-(S2) Master Thesis
Depositing User:	TRI IRVAN HARYADI
Date Deposited:	10 Aug 2024 02:40
Last Modified:	10 Aug 2024 02:40
URI:	http://repository.its.ac.id/id/eprint/114078

Actions (login required)

View Item