Graf 2-edge-colored dan Bilangan Kromatik Graf 2-edge-colored dengan Derajat Maksimal Terbatas

NABILA AULIA RAHMAN, Dr. Drs. Al. Sutjijana, M.Sc.

2025 | Skripsi | MATEMATIKA

Graf 2-edge-colored merupakan graf sederhana dengan dua jenis sisi, yaitu sisi positif dan sisi negatif. Homomorfisma graf 2-edge-colored $G$ ke graf 2-edge-colored H merupakan pemetaan yang memetakan setiap titik di G dengan titik di H dengan syarat jenis sisi atas titik yang dipetakan memiliki jenis yang sama. Bilangan kromatik dari graf 2-edge-colored G merupakan derajat terkecil dari graf 2-edge-colored H sedemikian hingga terdapat homomorfisma dari G ke H. Bilangan kromatik dari kelas graf 2-edge-colored atau graf bertanda merupakan bilangan kromatik maksimal dari graf yang ada di kelas tersebut. Pada tulisan ini dikaji bilangan kromatik graf 2-edge-colored berderajat maksimal terbatas. Secara lebih jelas, diberikan batas jelas untuk graf berderajat maksimal 1 dan 2.  Selain itu, diberikan batas atas secara spesifik untuk graf berderajat maksimal 3, 4, ... , k dengan k sebarang.

A 2-edge-colored graph is a simple graph with two types of edges, namely positive edges and negative edges. A homomorphism of a 2-edge-colored graph G to a 2-edge-colored graph H is a mapping that maps each vertex in G to a vertex in H with the condition that the type of edge being mapped corresponds to the same type. The chromatic number of a 2-edge-colored G is the smallest degree of a 2-edge-colored H such that there exists a homomorphism from G to H. The chromatic number of a class of 2-edge-colored graphs is the maximum chromatic number among the graphs in that class. This paper investigates the chromatic number of 2-edge-colored and signed graphs with bounded maximum degree. More specifically, a clear bound is provided for graphs with a maximum degree of 1 and 2. Additionally, specific upper bounds are given for graphs with a maximum degree of 3,4,..., k with any k.

Kata Kunci : Graf, Graf 2-edge-colored, Graf Target, Bilangan Kromatik, Homomorfisma