THE RIGID 3-RAINBOW COLORING OF SOME GRAPHS

• Main Author: Suci Nugrahani, Calista
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/87962
• Institution: Institut Teknologi Bandung

Let ???? be a simple, connected, and finite graph with order ?????3 and has an edge coloring. A path ???? in ???? is called a rainbow path if every edge in ???? has a different color. For a set ?????????(????), a Steiner path ???? is the shortest path that contains ????. A rigid 3-strong rainbow coloring is an edge coloring of ???? with the property for each set of ?????????(????) with |????|=3, there exists a rainbow Steiner path of ????. A graph ???? is called rigid 3-rainbow connected if ???? has a rigid 3-rainbow coloring. The minimum number of colors needed to make ???? has a rigid 3-rainbow coloring is called the rigid 3-rainbow coloring index, written as ????????????????3(????). It is obvious that not all graphs are able to have a rigid 3-rainbow coloring. As such, we provide the characteristics of rigid 3-rainbow connected graphs. In this final task, we provide an upper bound and a lower bound of ????????????????3(????) and determine the ????????????????3 of some simple graphs. Furthermore, we also study the ????????????????3 of graphs from edge comb operation ?????????????????? ???? of some connected graph ????. Some conditions for ???? are given such that ?????????????????? ???? is rigid 3-rainbow connected. Then, the upper bound and the lower bound of ????????????????3(?????????????????? ????) are studied. Additionally, we determine the ????????????????3(?????????????????? ????) for ???? is a fan graph ???????? with order ????+1 and cyclic graph ???????? with order ????.