Menentukan bilangan pewarnaan λ -backbone pada graf split

ABSTRAK

Pewarnaan titik pada graf G V (G), E (G) adalah pemberian warna untuk setiap titik pada graf sehingga tidak ada dua titik yang terhubung langsung berwarna sama Suatu pewarnaan titik f dari graf G disebut pewarnaan Backbone dari (G, H ) jika memenuhi f (u) f (v). Bilangan terkecil k dimana terdapat pewarnaan Backbone f : V
{1, 2, 3, ..., k } disebut bilangan pewarnaan Backbone dan dilambangkan dengan BBC (G, H ) . Graf yang digunakan dalam penelitian ini adalah graf split. Graf split adalah graf G yang himpunan titiknya dapat dipartisi kedalam clique dan himpunan bebas. Bentuk dari graf split merupakan sub bagian dari bagian graf perfect. Oleh karena itu graf split memenuhi(G)(G) . Selanjutnya, pada pokok bahasan nanti penulis akan menjelaskan tentang bagaimana menentukan bilangan pewarnaan λ -
backbone pada graf split.

Tulisan ini menyajikan proses atau langkah-langkah untuk menentukan bilangan pewarnaan λ -backbone pada graf split. Adapun langkah-langkahnya adalah sebagai berikut:
1. Menentukan graf split dan mengidentifikasi subgraf-subgraf komplit dan
bilangan khromatiknya.
2. Memberikan 1 contoh Spanning subgraph (Backbone) yang memuat subgraf komplit maksimum dari graf split dan memuat lintasan Hamilton.
3. Memberikan pewarnaan titik pada backbone lintasan Hamilton dari graf split.

Untuk penulisan skripsi selanjutnya, penulis menyarankan untuk mengkaji masalah penentuan bilangan pewarnaan -backbone pada graf yang lain misalnya graf kubus dengan menggunakan backbone yang lebih tinggi.