Vol. 18, No. 2,  161-168,  January, 2022 DOI: 10.20956/j.v18i2.14501

## Determination of Fractional Chromatic Numbers in the Operation of Adding Two Different Graphs
Penentuan Bilangan Kromatik Fraksional pada Operasi Penjumlahan Dua Graf berbeda
Junianto Sesa 1  , Siswanto 2 

## Abstract
The development of graph theory has given an enormous contribution to mathematics. One of which is graph coloring and its relevance spreads in various fields, namely index coding index theory  used  in  computing.  Fractional  coloring  presents  a  binary  pigment  at  a  vertex  with  a different color adjoining the other distinctive colors. In operating a graph, the process is done by summation. Vertex coloring can be applied to a graph that resulted from a certain chart. In this case, the graph summation outcome of the path graph and graph cycle will emerge into an identical  chromatic  fraction  number  as  the  sum  of  the  fractional  chromatic  numbers  on  each graph before it is operated, ( ) ( ) ( ) .
Keywords: Graph, Fractional, Chromatic

## Abstrak
Perkembangan teori graf telah banyak memberikan kontribusi kepada ilmu matematika, salah satunya  adalah  pewarnaan  graf,  dan  aplikasinya  yang  tersebar  dalam  berbagai  bidang  salah satunya  pada  teori  indeks  koding  yang  digunakan  pada  komputasi.  Pewarnaan  fraksional adalah  pemberian  warna  ganda  pada  titik  dengan  warna  yang  berbeda  dengan  titik  yang bertetangga  memiliki  warna  yang  berbeda.  Dalam  operasi-operasi  pada  graf  dikenal  adalah operasi  penjumlahan.  Pewarnaan  titik  dapat  diterapkan  pada  graf  yang  merupakan  hasil operasi dari beberapa graf khusus. Dalam hal ini graf hasil penjumlahan graf lintasan dan graf siklus  akan  menghasilkan  bilangan  kromatik  fraksional  yang  sama  dengan  penjumlahan bilangan kromatik fraksional masing-masing graf sebelum dioperasikan, ( ) ( ) ( ) .
Kata kunci: Graf, Fraksional, Kromatik
1  Department of Mathematics and Statisctics, Papua University Email address : j.sesa@unipa.ac.id 2  Departement of Statistics, Hasanuddin  University Email address : siswanto@unhas.ac.id

## Jurnal Matematika, Statistika & Komputasi
Junianto Sesa, Siswanto

## 1.  PENDAHULUAN
Teori  graf  merupakan  salah  satu  bagian  dari  ilmu  matematika  dan  dapat  digunakan  untuk menyelesaikan  permasalahan  diskrit.  Keunikan  teori  graf  adalah  kesederhanaan  pokok  bahasan yang  dipelajarinya,  karena dapat  disajikan  dalam  bentuk  pasangan  himpunan  benda-benda  yang disebut  titik  dan  yang  menghubungkan  titik  yaitu  garis-garis  yang  biasa  disebut  sisi.  Titik menggambarkan  objek-objek  tertentu  dan  sisi  menggambarkan  hubungan  antara  objek-objek tersebut [6].
Seiring  dengan  kemajuan  ilmu  pengetahuan  dan  teknologi  akhir-akhir  ini,  banyak  sekali penelitian  terbaru  tentang  graf,  mulai  dari  jenis-jenis  graf,    pewarnaan  graf,  bilangan  ramsey, differensial  graf,  dan  lain-lain.  Aplikasinya  yang  tersebar  dalam  berbagai  bidang  seperti  pada jaringan  media  sosial,  dan  kampanye  politik.  Bilangan  kromatik  fraksional  diperoleh  setelah memberi warna ganda pada setiap titik di graf sedemikian sehingga setiap titik yang diberi warna ganda  berbeda  jika  titik  tersebut  bertetangga  dan  banyaknya  warna  minimum  yang  digunakan disebut bilangan  kromatik fraksional [10].
Graf cocktail party merupakan graf pertama yang ditemukan bilangan kromatik fraksionalnya oleh  Roberts  [17],  namun  kekurangannya  adalah  tidak  menjelaskan  secara  mendalam  mengenai batasan  dalam  mewarnai.  Pada  1979  Bollobás  dkk  [20],  juga  menemukan  bilangan  kromatik fraksional  graf  web,  helm,  bipartit,  dan  tripartit  dengan  menjelaskan  lebih  rinci bahwa  bilangan kromatik fraksional tidak hanya bilangan bulat tetapi ada juga dalam pecahan. Setelah itu, Saaty dkk  [13]  menentukan  bilangan  kromatik  graf  Pan  dengan  menerapkan  empat  warna  dalam  satu titik.
Pada  tahun  1990  Skiena  [15]  menemukan  bilangan  kromatik  fraksional  pada  graf  siklus, bintang  dan  roda  sekaligus  menjelaskan  perbandingan  antara  bilangan  kromatik  dan  bilangan kromatik  fraksional,  Selanjutnya,  Larsen  dan  Ullman  [14]  mengembangkan  kontruksi  graf Mycielski  dan  mencari  bilangan  kromatik  fraksionalnya,  hingga  sekarang  Ullman  masih menggeluti bidang ini dimana sekarang beliau sedang  menyusun buku dengan judul “Fractional Graph Theory” yang berisi seluruh pembahasan pewarnaan fraksional.
Godsil  dan  Royle  [10]  juga  meneliti  bilangan  kromatik  fraksional  dari  graf  lintasan  dengan mengambil  dasar  dari  beberapa  peneliti  sebelumnya.  Dengan  berjalannya  waktu  Pirnazar  dan Ullman  [16]  kembali  menemukan  bilangan  kromatik  fraksional  pada  graf  planar  dengan mengkontruksi beberapa graf diantaranya adalah graf bintang dan graf lengkap. Golin [11] juga pada  tahun  2004  mengembangkan  pewarnaan  fraksional  dengan  menerapkannya  pada  graf antiprisma dan graf pohon kemudian membandingkan hasilnya.
Dengan  berkembangnya  banyak  kontruksi  graf  baru maka  peneliti  dibidang  pewarnaan  graf juga semakin giat dalam mencari bilangan kromatik fraksional dari graf-graf tersebut. Ghost dkk [9] pada tahun 2006 meneliti bilangan kromatik dari graf barbel. Kemudian disusul oleh Bryant [5]  Bilangan  kromatik  fraksional  graf  lengkap  dengan  menerapkan  unsur  ketetanggaan.  Pada tahun 2008 Anitha [1] diperoleh lagi bilangan kromatik fraksional graf matahari dan graf sunlet, diikuti  pada  tahun  2011  Ullman  dkk  [18]  kembali  meneliti  bilangan  kromatik  fraksional  graf kneser, kosong, dan prisma.
Dengan berkembangnya dunia teknologi maka banyak peneliti mulai melirik beberapa bentuk graf yang bisa diaplikasikan kedalam perangkat-perangkat modern. salah satunya adalah bilangan kromatik  fraksional,  dimana  beberapa  peneliti  sudah  tidak  mengkontruksi  graf  baru  tetapi mencari dimana dapat diaplikasikan hasil penelitian mengenai pewarnaan graf. Pada tahun 2013 Graf -free  [8]  yang  merupakan  kontruksi  dari  graf  kneser  dipakai  dalam  indeks  pengkodean dimana yang ditinjau adalah bilangan kromatik fraksionalnya, dijelaskan bahwa dalam membuat indeks  pengkodean  yang  paling  optimal  yaitu  dengan  menggunakan  pewarnaan  fraksional. Kemudian  Zdenek  Dvorak  dkk  [7]  juga  menemukan  bilangan  kromatik  fraksional  pada  Graf Subcubic triangle-free dimana diaplikasikan pada pemrograman komputasi. Tahun 2014 banyak

## Jurnal Matematika, Statistika & Komputasi
Junianto Sesa, Siswanto
peneliti  mulai  tertarik  mengkontruksi  beberapa  graf  menjadi  satu  graf  baru  sesuai  dengan bentuk yang diinginkan agar dalam diaplikasikan dalam indeks kode, salah satunya adalah Kneser Hyper Graf [2] yang juga merupakan kontruksi dari graf kneser.
Hingga saat ini banyak peneliti telah mengeluarkan jurnal yang berkaitan dengan pewarnaan fraksional yang diaplikasikan dalam bidang komputer, salah satunya oleh Fatemeh Arbabjolfaei dan  Young-Han  Kim  [3]  pada  tahun  2015,  menjelaskan  bahwa  masalah  indeks  kode  khusus kapasitas region  dari  masalah  yang  terkecil  pada saat terjadi interaksi  yang  tidak  ada,  satu jalur ataupun yang kompleks dapat diselesaikan menggunakan pewarnaan fraksional dimana bilangan kromatik fraksional yang kecil sangat membantu dalam pembuatan indeks kode.
Pada  tahun  2018  Junianto  dkk  [12]  juga  melakukan  penelitian  untuk  menentukan  bilangan kromatik  fraksional  dari  operasi  amalgamasi  graf  lintasan  dan  graf  siklus,  penelitian  tersebut terbagi atas dua yaitu, amalgamasi sisi dan amalgamasi titik.
Berdasarkan  uraian  diatas  penulis  tertarik  untuk  melihat  bilangan  kromatik  fraksional  graf hasil dari operasi penjumlahan dua graf berbeda, yang akan menghasilkan satu graf baru sehingga bilangan  kromatik  dari  graf  tersebut  akan  dipengaruhi  oleh  salah  satu  bilangan  kromatik fraksional dari salah satu graf sebelum dioperasikan.
Agar  dapat  memahami  mengenai  pewarnaan  pada  graf  serta  operasi  penjumlahan,  maka diberikan beberapa definisi dan teorema berkaitan dengan pembahasan tersebut.
Definisi  1.1. Graf  G  adalah  pasangan  (V(G),  E(G)),  dimana  V(G)  adalah  himpunan  berhingga tidak  kosong,  yang  elemen-elemennya  disebut  titik,  dan  E(G)  adalah  himpunan  pasangan- pasangan tak berurut dari elemen-elemen V(G) yang berbeda disebut sisi [6].
Definisi  1.2. Pewarnaan  titik  adalah  memberikan  warna  pada  titik-titik  pada  graf    sedemikian sehingga setiap dua titik yang bertetangga mempunyai warna yang berbeda .
Definisi  1.3. diberikan  graf  tak  berarah  G  =  (V,  E), himpunan bebas  adalah  himpunan  bagian dari titik , sedemikian sehingga tidak ada dua titik di U yang bertetangga [4].
Definisi  1.4. Bilangan  kromatik  fraksional  pada  graf  sederhana (    ) didefinisikan  dengan ( ) diberikan oleh ∑ ∑ , - ( )   | ⋃ |
Dengan I himpunan dari semua himpunan bebas di G, bilangan riil positif [20]. Definisi  1.5. Graf  jumlah adalah  graf  baru  dengan  himpunan  titik (     )    ( ) ( ) dan himpunan sisi (     )    ( )    ( )   *         ( )       ( )+ [6]. Contoh 1.1.
Gambar 1.1. Contoh operasi Penjumlahan graf
A 𝑩 𝑪 𝟏 𝟐

## Jurnal Matematika, Statistika & Komputasi
Junianto Sesa, Siswanto

## 2. DISKUSI
Dalam  mencari  bilangan  kromatik  fraksional  graf  dengan  menggunakan  metode  kajian pustaka, langkah - langkah yang digunakan dalam penelitian ini adalah :
1. Mengumpulkan bahan literatur serta studi kepustakaan yang berhubungan dengan graf.
2. Menggambar graf tak terhubung tanpa loop untuk dan dengan n adalah titik dan m adalah garis.
3. Mengelompokkan graf tak terhubung untuk garis maksimal yang sama.
4. Menghitung jumlah graf tak terhubung untuk setiap garis.
5. Melihat pola banyaknya graf yang terbentuk.
6. Memberi warna pada titik graf (dalam 1 titik lebih dari satu warna)
7. Menarik kesimpulan.
Seperti  diketahui  bahwa  bilangan  kromatik  fraksional  pada  setiap  graf  ada  yang  bernilai bilangan bulat tetapi ada juga yang merupakan pecahan. Pewarnaan Fraksional merupakan topik baru  dari  generalisasi  pewarnaan  graf  biasa  di  teori  graph  yang  dikenal  sebagai  teori  graf fraksional. Dalam pewarnaan graf fraksional, setiap titik dalam graf diberi beberapa warna, dan titik    yang  bertetanga  atau  terhubung  oleh  sisi  harus  diberi  warna  yang  berbeda.  Namun  dalam pewarnaan  fraksional,  satu  himpunan  diberi  warna  yang  sama  pada  setiap  titik  dari  graf. Pewarnaan  fraksional  graf  dapat  dilihat  sebagai  relaksasi  pemrograman  linear  dari  pewarnaan graf.  Masalah  pewarnaan  fraksional  jauh  lebih  baik  digunakan  untuk  pendekatan  pemrograman linear dari masalah pewarnaan biasa.
Graf seringkali dikontruksi sesuai dengan kebutuhan sedemikian sehingga membentuk suatu graf yang dapat diaplikasikan dalam dunia teknologi, maka sering di gunakan operasi graf dalam mengkontruksi.
Bilangan  kromatik  fraksional  pada  operasi  penjumlahan  graf  lintasan  dan  graf  siklus  yang sebagai berikut,
a) Misal diberikan graf lintasan dengan ( )   * + dan ( )   * + dan graf  siklus dengan ( )   * + dan ( )   * + ,  maka himpunan bebas minimum dari adalah * + * +
* +
* + * + maka himpunan dari semua himpunan bebas * + . diberikan ( )   , - *   + *   + dan ( )   , - *   + *   + *    +
, - ( ) | | ( ) | | ( ) | ( )| ( ) | ( )|

## Jurnal Matematika, Statistika & Komputasi
Junianto Sesa, Siswanto
( ) | ( )|
maka bilangan fraksional adalah
∑
Diberikan ( )   , -
*     +
*     + dan ( )   , - *     + *        + *        + , - ( ) | |
( ) | |
( ) | ( )| ( ) | ( )| ( ) | ( )|
maka bilangan fraksional adalah
∑
diberikan ( )   , -
*       +
*       + dan ( )   , - *          + *           + *           + , - ( ) | | ( ) | |
( ) | ( )|
( ) | ( )|
( ) | ( )|
maka bilangan fraksional adalah
∑
diberikan ( )   , - *         + *          + dan ( )   , - *              + *              + *              + , -

## Jurnal Matematika, Statistika & Komputasi
Junianto Sesa, Siswanto
( ) | | ( ) | |
( ) | ( )| ( ) | ( )| ( ) | ( )|
maka bilangan fraksional adalah
∑
dst. Sehingga bilangan fraksionalnya *             + , dan bilangan kromatik fraksionalnya
∑
*             +
untuk lebih jelas perhatikan gambar berikut ini
Gambar 2.1. Bilangan Kromatik Fraksional Graf
Berdasarkan hasil diatas maka diperoleh teorema sebagai berikut

## Teorema 2.1
Jika graf hasil operasi penjumlahan graf lintasan dan graf siklus maka bilangan kromatik fraksionalnya adalah ( ) ( ) ( ) .
Bukti: Misal  diberikan  graf  lintasan dan  graf  siklus ,  jika merupakan  graf  hasil  operasi penjumlahan graf siklus dan graf lintasan maka setiap titik pada graf bertetangga pada setiap titik pada graf , sehingga titik graf diberi warna berbeda dengan graf . Selanjutnya untuk menentukan bilangan kromatik fraksional penjumlahan graf dan adalah dengan menetukan bilangan  kromatik  fraksional  masing-masing  graf  sebelum  dijumlahkan,  diperoleh ( ) dan
( ) .  Karena  setiap  titik bertetangga  dengan  titik maka  bilangan  kromatik  fraksional
( ) ( ) ( ) .

## 3.  KESIMPULAN
Bilangan kromatik fraksional sangat berguna dalam dunia teknologi terutama dibidang indeks kode.  Bilangan  kromatik  fraksional  dari  beberapa  graf  jika  digabung  menggunakan  operasi penjumlahan  maka  hasilnya  adalah  jumlah  bilangan  kromatik  fraksional  setiap  graf  sebelum dilakukan operasi.

## Jurnal Matematika, Statistika & Komputasi
Junianto Sesa, Siswanto

## REFERENCES
[1]  Anitha R., & Lekshmi R S., 2008. N-Sun Decomposition of Complete, Complete Bipartite and  Some  Harary  Graphs. International  Journal  of  Computational  and  Mathematical Sciences, Vol. 2, No. 1, 33-38.
[2]  Araujo-Pardo  G.,  Diaz  P  J  C.,  &  Oliveros  D.,  2016.  The  (p,  q)-extremal  Problem  and  the Fractional Chromatic Number of Kneser Hypergraphs. Discrete Mathematics, Vol. 339, No. 11, 2819-2825.
[3]  Arbabjolfaei F., & Kim Y H., 2015. Structural Properties of Index Coding Capacity Using Fractional Graph Theory. IEEE International Symposium on Information Theory (ISIT) , thn 2015, 1034-1038. University of California, San Diego.
[4]  Bondy  J  A.,  1978.  A  remark  on  two  sufficient  conditions  for  Hamilton  cycles. Discrete Mathematics , Vol. 22, No. 2, 191-193.
[5]  Bryant  D.,  Cycle  Decompositions  of  Complete  Graphs. London  Mathematical  Society Lecture Note, 346, 67. Cambridge, England.
[6]  Chartrand G., 1985. Introductory Graph Theory. Dover, New York.
[7]  Dvorak  Z.,  Sereni  J  S.,  &  Volec  J.,  2014.  Subcubic  Triangle-free  Graphs  have  Fractional Chromatic Number at Most 14/5. Journal of the London Mathematical Society, Vol. 89, No. 3, 641-662.
[8]  Edwards K., & King A D., 2013. Bounding the Fractional Chromatic Number of Free Graphs. Siam Journal on Discrete Mathematics, Vol. 27, No. 2, 1184-1208.
[9]  Ghosh  A.,  Boyd  S.,  &  Saberi  A.,  2008.  Minimizing  Effective  Resistance  of  a Graph. Proceeding  17th  International  Symposium  Mathematics  the  Network  and  Systems, thn 2008, 37-66. Kyoto, Japan .
[10]  Godsil C., & Royle G., 2001. Fractional Chromatic Number . Springer Verlag, New York.
[11]  Golin  M J.,  &  Leung  Y  C.,  2004.  Unhooking  Circulant  Graphs:  A  Combinatorial  Method for  Counting  Spanning  Trees  and  Other  Parameters. International  Workshop  on  Graph- Theoretic Concepts in Computer Science, thn 2004, 296-307. Springer, Heidelberg, Berlin.
[12] Junianto  S.,  Armin  L.,  Hasmawati  &  Siswanto.,  2018.  Determination  of  Fractional Chromatic  Number  on  Two  Different  Graphs  of  Amalgamation  Operation. International Journal of Computer Science and Network . Vol. 7, No.3, 158-165.
[13]  Kainen  P  C.,  &  Saaty  T  L.,  1977. The  Four-Color  Problem:  Assaults  and Conquest. McGraw Hill, New York.
[14]  Larsen M., Propp J., & Ullman D., 1995. The Fractional Chromatic Number of Mycielski's Graphs. Journal of Graph Theory, Vol. 19, No. 3, 411-416.
[15]  Pemmaraju  S.,  &  Skiena  S.,  2003.  Cycles,  Stars,  and  Wheels. Computational  Discrete Mathematics Combinatiorics and Graph Theory in Mathematica , 249-284.
[16]  Pirnazar  A.,  &  Ullman  D  H.,  2002.  Girth  and  Fractional  Chromatic  Number  of  Planar Graphs. Journal of Graph Theory, Vol. 39, No. 3, 201-217.
[17]   Roberts  F  S.,  1969.  On  the  Boxicity  and  Cubicity  of  a  Graph. Recent  Progress  in Combinatorics, Vol. 1, No. 1, 301-310.
[18]  Scheinerman E R., & Ullman D H., 2011. Fractional Graph Theory a Rational Approach to the Theory of Graphs. Dover, New York.

## Jurnal Matematika, Statistika & Komputasi
Junianto Sesa, Siswanto
[19]  Shanmugam  K.,  Dimakis  A  G.,  &  Langberg  M.,  2013.  Local  Graph  Coloring  and  Index Coding. IEEE  International  Symposium  on  Information  Theory ,  thn  2013,  1152-1156. Department of Mathematics and Computer Science the Open University of Israel, Israel.
[20]  Weisstein  E  W.,  2011.  Fractional  Chromatic  Number.  https://mathworld.  wolfram.  com/. [11 Juni 2021].