Bilangan Diakromatik Pada Beberapa Graf Asiklik

Raventino, Dr. rer.nat. Yeni Susanti, M.Si

2024 | Tesis | S2 Matematika

Pewarnaan lengkap adalah pewarnaan titik dengan syarat setiap pasangan warna berbeda muncul minimal satu kali. Tujuan tesis ini adalah memperoleh maksimum banyaknya warna yang dapat digunakan dalam mewarnai suatu graf berarah asiklik pada pewarnaan lengkap yang disebut bilangan diakromatik. Untuk memperoleh bilangan diakromatik suatu graf berarah asiklik, dibutuhkan syarat yaitu banyaknya pasangan warma harus kurang dari atau sama dengan banyaknya busur graf tersebut. Pada tesis ini, dikaji tentang bilangan diakromatik beberapa graf berarah, meliputi graf lobster berarah, graf kembang api berarah, dan graf pohon pisang berarah. Untuk masing-masing graf berarah, ditinjau bilangan diakromatik untuk orientasi arah tertentu dan orientasi arah sebarang.

A complete coloring is a vertex coloring where each pair of different colors appears at least once. This thesis aims to determine the maximum number of colors that can be used to completely color an acyclic directed graph, known as the diachromatic number. To achieve the diachromatic number, the number of color pairs must be less than or equal to the number of arcs in the graph. This thesis investigates the diachromatic numbers of various directed graphs, including the directed lobster graph, directed fireworks graph, and directed banana tree graph. For each type of directed graph, the diachromatic numbers are analyzed for both specific and arbitrary direction orientations.

Kata Kunci : Pewarnaan Titik, Pewarnaan Lengkap, Maksimum Banyaknya Warna