## Pewarnaan Titik Ketakteraturan Lokal Graf Pensil

## On the Local Irregularity Vertex Coloring of Pencil Graphs
Guntari Saputra 1 , Arika Indah Kristiana 2 , Robiatul Adawiyah 3 , Arif Pujiyanto 4 , Laela Nur ‘Aini 5 , Israul Laila 6 , Rahma Dila 7
guntarisaputra594@gmail.com
1,2,3,4,5 Universitas Jember, 6,7 Universitas Malikussaleh
Abstrak Graf yang digunakan dalam penelitian ini merupakan graf sederhana dan terhubung yang  terdiri  dari  himpunan  titik dan  himpunan  sisi Sebuah  fungsi disebut  pelabelan  ketakteraturan  titik  dan .  Jika untuk  setiap , dimana dan maka disebut pewarnaan  titik  ketakteraturan  lokal.  Bilangan  kromatik  dari  pewarnaan  titik ketakteraturan lokal graf   dinotasikan dengan
yaitu kardinalitas minimum label terbesar dari seluruh pewarnaan titik ketakteraturan lokal tersebut. Dalam atikel ini  kita  akan  belajar  tentang  pewarnaan  titik  ketakteraturan  lokal  graf  pensil  serta menemukan nilai eksak dari bilangan kromatiknya.
Kata kunci: ketakteraturan lokal; pewarnaan titik; graf pensil.
Abstract The graph used in this paper is a simple and connected graph consisting of a set of vertices and a set of  edge .  A  function is  called  vertex  irregulaarity  labelling  and .  If  for  every , where and then, f is called local irregularity vertex  coloring.  The  chromatic  number  of  the  local  irregular  vertex  coloring  of  graph    is  denoted  by
, which is the minimum cardinality of the largest label of all local irregular vertex coloring. In this article  we  will learn about  coloring points of local irregularities in pencil  graphs and finding  the  exact value of the chromatic number.
Keywords : local irregularity; vertex coloring; pencil graphs

## PENDAHULUAN
Graf  merupakan  ilmu  terapan  dari  ilmu  matematika.  Teori  Graf pertama  kali  muncul  oleh  matematikawan  asal  Swiss  yaitu  Leonhard  Euler dalam menyelesaikan permasalahan Jembatan Konigsberg. Daniel dan Taneo (Azahra,  2020)  menyebutkan  bahwa  graf  digunakan  untuk  menggambarkan objek-objek  diskrit  dan  keterkaitannya  antar  objek-objek tersebut.  Graf adalah suatu himpunan yang terdiri dari humpunan dan , dimana adalah  himpunan  tak  kosong  yang  disebut  titik  sedangkan  sedangkan adalah    himpunan    dari  pasangan  tak  terurut yang  boleh  kosong yang  disebut  sisi.  Berdasarkan  definisi  diatas  dapat  disimpulkan  bahwa
sebuah graf dimungkinkan tidak mempunyai sisi dan hanya mempunyai satu titik  (Agustin,  2021).  Pewarnaan  graf  merupakan  salah  satu  kasus  dari pelabelan graf, yang dilakukan dengan cara memberikan warna pada titik-titik yang ada pada batas tertentu (Adawiyah, 2021). Warna yang digunakan pada pewarnaan  graf  berupa  himpunan  bilangan  bulat  positif,  seperti  {1,2,  ... k }. Pada  pewarnaan  graf  terdapat  istilah  bilangan  kromatik .  Apabila terdapat sebuah graf   yang memiliki   warna, maka bilangan kromatik yang dimaksud merupakan bilangan   atau jumlah warna minimum/terkecil pada graf    sedemikian  hingga  dua  titik/sisi/wilayah  yang  bertetangga  tidak memiliki warna yang sama (Chatrand, 2020).
Pewarnaan graf  terdiri tiga jenis  yaitu pewarnaan  titik, pewarnan  sisi dan  pewarnaan  wilayah.  Pewarnaan  titik  pada  graf  adalah  memberikan warna  berbeda  pada  titik  yang  saling  bertetangga  (Daniel,  2019;  Ramane, 2020).  Pewarnaan  titik  dilakukan  dengan  memberikan  warna  pada  tiap  titik sedemikian hingga setiap dua titik yang bertetangga mempunyai warna yang berbeda.  Jumlah  warna  minimum  yang  digunakan  dalam  pewarnaan  titik disebut sebagai bilangan kromatik dari graf   yang dinotasikan dengan Dalam  pewarnaan  graf,  khususnya  pewarnaan  titik,  terdapat  beberapa pengembangan  dengan  menambahkan  syarat  tertentu,  misalnya  pewarnaan lokasi.  Konsep  pewarnaan  lokasi  suatu  graf  mengaitkan  konsep  pewarnaan titik dan dimensi partisi (Hartsfield, 1990). Pewarnaan sisi dari sebuah graf G adalah  pemberian  warna  pada  sisi  dimana  sisi  yang  bertetangga  (sisi  yang bersisian pada titik yang sama) memiliki warna yang berbeda (Hartsfield, N. dan  Ringel,  G.,  1994).  Menurut  Chaltrand  dan  Lesniak  (1996)  bahwa  jika terdapat  minimal k warna  pada  pewarnaan  wilayah  maka  disebut k - pewarnaan  wilayah  (Munawaroh,  2022).  Pewarnaan  titik  di 𝐺 merupakan pewarnaan  lokasi  jika  kode  warna  titik-titik  di 𝐺 berbeda  (Waluyo,  2023). Pewarnaan  lokasi  pada  suatu  graf  tidak  hanya  bertujuan  mencari  apakah suatu  graf  dikatakan  memenuhi  definisi  pewarnaan  lokasi  saja,  tetapi  juga untuk  mendapatkan  warna  minimum  (banyaknya  warna)  pada  pewarnaan lokasi  tersebut  yang  selanjutnya  dinamakan  bilangan  kromatik  lokasi (Kritiana,  2023).  Jadi bilangan kromatik  adalah bilangan    terkecil sehingga graf dapat  diwarnai  dengan warna.  Biasanya  warna-warna  yang digunakan  untuk  mewarnai  suatu  graf  dinyatakan  dengan Pelabelan  pada  graf    didefinisikan  sebagai  fungsi . Fungsi disebut  pelabelan  titik.  Selanjutnya  pada  penelitian  ini dikembangkan  pewarnaan  titik  ketakteraturan  lokal  pada  graf.  Pewarnaan titik  ketakteraturan  lokal  ini  merupakan  penggabungan  konsep  pewarnaan titik dan pelabelan ketakteraturan jarak. Pewarnaan titik ketakteraturan lokal dilakukan  dengan  meminimumkan  label  titik  dan  meminimumkan  jumlah
warna titik pada graf. Definisi dari pewarnaan titik ketakteraturan lokal yang digunakan pada penelitian ini dapat dilihat pada definisi berikut ini
Definisi  1. (Kristiana,  2023) Misalkan merupakan fungsi label dan fungsi bobot dimana Fungsi   disebut pewarnaan titik ketakteraturan lokal, jika: i. ii. untuk setiap , Definisi  2. (Kristiana,  2023) Bilangan  kromatik  ketakteraturan  lokal  yang dinotasikan  dengan yaitu  kardinalitas  minimum  pewarnaan  titik
ketakteraturan lokal
Lemma 1. (Kristiana, 2023) Misalkan graf    merupakan graf  terhubung dan sederhana, maka
Azzahra,  et.al, telah  meneliti  bilangan  kromatik  ketakteraturan  lokal pada  graf  ladder,  graf  helm,  dan  beberapa  graf  grid  lainnya.  Pada penelitiannya  tersebut  salah  satu  teorema  yang  diperoleh  yakni  bilangan kromatik ketakteraturan lokal pada graf ladder   yaitu 4 dengan .

## METODE
Jenis  penelitian  ini  merupakan  penelitian  eksploratif.  Penelitian eksploratif merupakan penelitian yang menemukan hal-hal baru yang bersifat eksplorasi.  Metode  yang  digunakan  dalam  penelitian  ini  adalah  metode deduktif  aksiomatik.  Metode  deduktif  aksiomatik  merupakan  metode  yang menggunakan  beberapa  pembuktian  yang  bersifat  deduktif  yang  berlaku dalam logika matematika. Metode ini menggunakan aksioma, postulat, atau teorema yang sudah ada guna membuktikan permasalahan yang diteliti. Pada prosesnya,  penelitian  ini  menggunakan  pendeteksian  pola  tertentu  sehingga permasalahan yang ada dapat dirumuskan dan diperoleh bentuk umumnya.

## HASIL DAN PEMBAHASAN
Pada artikel ini dihasilkan teorema pewarnaan titik ketakteraturan lokal pada graf pensil. Graf pensilnya berupa graf pensil dengan raut.
Observasi  1. Diberikan adalah  graf  pensil  raut  tunggal  dan adalah  graf pensil  raut  ganda.  Untuk  setiap  bilangan  bulat  positif ,  dan
Jurnal Axioma: Jurnal Matematika dan Pembelajaran Volume 9 No 1 Januari 2024 E ISSN 2615-0697 dan P ISSN 2622-8149 97 - 105
Teorema  1. Diberikan adalah graf pensil raut tunggal. Untuk setiap bilangan bulat positif , . Bukti. Graf merupakan graf sederhana dan terhubung dengan himpunan titik dan himpunan sisi . Graf pensil mempunyai  kardinalitas  titik  yakni ,  serta  mempunyai kardinalitas sisi yaitu . Derajat minimum dari graf adalah dan derajat maksimum dari graf adalah . Jika  semua  titik  dilabeli  oleh  1  maka  kita  mempunyai dan .  Hal  ini  kontradiksi dengan definisi 1, sejak , . Oleh karena itu, . Berdasarkan  lemma  1,  batas  bawah  untuk  bilangan  kromatik .  Jadi, .  Sementara  itu,  batas  atas  untuk bilangan kromatik ketakteraturan lokal, kami mendefinisikan dengan 2-pelabelan titik ketakteraturan sebagai berikut:
Oleh  karena  itu,
.  Pelabelan  ini  memberikan  bobot  titik  sebagai
berikut:
i. Untuk   gasal

## ii. Untuk   genap
Gambar 1. Pewarnaan Titik Ketakteraturan Lokal Graf
Untuk  setiap ambil ,  dan untuk , maka . Ambil , dan untuk maka .  Ambil ,  dan untuk maka .  Selain  itu,  jika dan maka ,  kemudian  jika dan maka . Berdasarkan  hal  tersebut,  diperoleh  himpunan  bobot  titik  graf  pensil adalah , jadi . Sehingga . ◼ Teorema  2. Diberikan adalah  graf  pensil  raut  ganda.  Untuk  setiap  bilangan bulat positif , Bukti. Graf merupakan  graf  sederhana  dan  terhubung  dengan himpunan  titik dan  himpunan  sisi . Graf  pensil  mempunyai  kardinalitas  titik  yakni ,  serta mempunyai kardinalitas sisi yaitu . Derajat minimum dari
graf adalah dan  derajat  maksimum  dari  graf adalah . Langkah pertama untuk membuktikan teorema tersebut yaitu mencari batas bawah dari pewarnaan ketakteraturan lokal graf pensil. Jika semua titik dilabeli oleh 1 maka kita mempunyai dan .  Hal  ini  kontradiksi dengan definisi 1, sejak , . Oleh karena itu, . Berdasarkan  lemma  1,  batas  bawah  untuk  bilangan  kromatik .  Jadi, .  Sementara  itu,  batas  atas  untuk bilangan kromatik ketakteraturan lokal, kami mendefinisikan dengan 2-pelabelan titik ketakteraturan sebagai berikut :
Oleh  karena  itu, .  Pelabelan  ini  memberikan  bobot  titik  sebagai berikut:
i. Untuk   gasal
ii. Untuk   genap
Gambar 2. Pewarnaan Titik Ketakteraturan Lokal Graf
Untuk  setiap ambil ,  dan untuk maka . Ambil , dan untuk maka .  Ambil ,  dan untuk maka .  Selain  itu,  jika dan maka ,  kemudian  jika dan maka .  Jika dan ,  maka ,  lalu  jika dan ,  maka . Berdasarkan hal tersebut, diperoleh himpunan bobot titik graf pensil adalah ,  jadi .  Sehingga . ◼

## KESIMPULAN DAN SARAN
Dalam  paper  ini  kita  telah  belajar  tentang  pewarnaan  titik ketakteraturan lokal pada graf pensil. Kesimpulan yang diperoleh yakni, nilai eksak  bilangan  kromatik  ketakteraturan  lokal  pada  graf  pensil  raut  tunggal adalah untuk . Pada graf pensil raut ganda memiliki nilai eksak  bilangan  kromatik  ketakteraturan  lokal  adalah untuk

## DAFTAR PUSTAKA
A’yun, Q., Adawiyah, R., Agustin, I. H., & Albirri, E. R. (2021, March). On the irregular coloring of bipartite graph and tree graph families. In Journal of Physics: Conference Series (Vol. 1836, No. 1, p. 012024). IOP Publishing.
Adawiyah, R., Prihandini, R. M., Albirri, E. R., Agustin, I. H., & Alfarisi, R.
(2019,  March).  The  local  multiset  dimension  of  unicyclic  graph.  In IOP Conference  Series:  Earth  and  Environmental  Science (Vol.  243,  No.  1,  p. 012075). IOP Publishing.
Agustin,  I.  H.,  Adawiyah,  R.,  &  Kurniawati,  E.  Y.  (2021,  March).  On  the study  of  local  antimagic  vertex  coloring  of  graphs  and  their  operations. In Journal of Physics: Conference Series (Vol. 1836, No. 1, p.  012018). IOP Publishing.
Azahra,  Nadia.,  Kristiana  I.A.,  Dafik.,  Alfarisi,  R.  2020.  On  The  Local Irregularity  Vertex  Coloring  of  Related  Grid  Graph.  International Journal of Academic and Applied Research (IJAAR).
Chartrand, G., Erwin, D., Henning, M. A., Slater, P. J., & Zhang, P. (2002). The  locating-chromatic  number  of  a  graph.  Bull.  Inst.  Combin.  Appl, 36(89), 101.
Chartrand,  G.,  English,  S.,  &  Zhang,  P.  (2017).  Kaleidoscopic  colorings  of graphs. Discussiones Mathematicae Graph Theory , 37 (3), 711-727. F. Daniel and P. Taneo, Teori Graf. Deepublish, 2019. Fran.Fransiskus.,Kabang.K.N.,Yundari.  2021.’’Bilangan  Kromatik  Lokasi Pada Graf Total Dan Graf Splitting Dari Graf Bintang,’’ Teorema: Teori dan Riset Matematika
H. S. Ramane, V. V. Manjalapur, and I. Gutman, “General sum -connectivity index,  general  product-connectivity  index,  general  zagreb  index  and coindices  of  line  graph  of  subdivision  graphs,”  AKCE  International Journal of Graphs and Combinatorics, vol. 14, no. 1, pp. 92 – 100, 2020. Hartsfield, N. dan G. Ringel. 1990. Pearls in Graph Theory A Comprehensive Introduction. New York: Academic Press, Inc.
K.  Munawaroh,  A.  I. Kristiana,  E.  R.  Albirri,  D.  Dafik,  and  R.  Adawiyah, “Pewarnaan  titik  ketakteraturan  lokal  pada  keluarga  graf  unicyclic,” Cgant Journal of Mathematics and Applications, vol. 2, no. 2, pp. 6 – 21,
2022.
Kristiana  I.  A.,  Dafik.,  Utoyo  M.  I.,  Slamin.,  Alfarisi  R.,  Agustin  H.I.,  dan Venkatachalam  M. 2019. Local  Irregularity Vertex Coloring of  Graphs. International  Journal  of  Civil  Engineering  and  Technology(IJCIET). 10(4):451-461
Kristiana,  A.  I.,  Anzori,  A.,  Adawiyah,  R.,  Slamin,  S.,  &  Albirri,  E.  R. (2023).  Bilangan  Kromatik  Graceful  Pada  Keluarga  Graf  Grid. Jurnal Axioma: Jurnal Matematika dan Pembelajaran , 8 (2), 144-155. Kristiana,  A.  I.,  Aji,  A.,  Wihardjo,  E.,  &  Setiawan,  D.  (2022).  on  Graceful Chromatic  Number  of  Vertex  amalgamation  of  Tree  Graph Family. CAUCHY: Jurnal Matematika Murni dan Aplikasi , 7 (3), 432-444.
Kristiana,  A.  I.,  Mursyidah,  I.  L.,  Dafik,  D.,  Adawiyah,  R.,  &  Alfarisi,  R. (2023).  Local  irregular  vertex  coloring  of  comb  product  by  path  graph and  star  graph. Discrete  Mathematics,  Algorithms  and  Applications , 15 (06), 2250148.
Kristiana, A. I., Utoyo, M. I., Dafik, D., Alfarisi, R., & Waluyo, E. (2022). On  the  $  r  $-Dynamic  Chromatic  Number  of  Corona  Product  of  Star Graph. Thai Journal of Mathematics , 20 (3), 1389-1397
Mercy,  M.  H.,  &  Arputhamary, I. A. (2023). Rainbow  Connection Number of Corona Product of Pencil Graphs P m ∘ Pc n, K m ∘ Pc n and C m ∘ Pc
Jurnal Axioma: Jurnal Matematika dan Pembelajaran Volume 9 No 1 Januari 2024 E ISSN 2615-0697 dan P ISSN 2622-8149 97 - 105
n. In Mathematical and Computational Intelligence to Socio-scientific Analytics and Applications (pp. 185-194). Singapore: Springer Nature Singapore. Nuroeni,  I.,  Kristiana,  A.  I.,  Hussen,  S.,  Setiawani,  S.,  &  Adawiyah,  R. (2023). Local Irregularity Point Coloring On The Result Of Subdivision Operation Of Helm Graphs. Jurnal Diferensial , 5 (2), 117-125.
Parvathi, N., & Rani, A. V. (2018, April). Upper bound for the span of pencil graph. In Journal of Physics: Conference Series (Vol. 1000, No. 1, p. 012032).
IOP Publishing.
Pratama,  P.  A.  C.  (2022). Kajian  Bilangan  Kromatik  Graceful  Untuk  Graf C_m× P_n (Doctoral dissertation, Universitas Pendidikan Ganesha). Simamora,  D.  N.,  &  Salman,  A.  N.  M.  (2015).  The  rainbow  (vertex) connection  number  of  pencil  graphs. Procedia  Computer  Science , 74 ,  138- 142.
Slamin.  2009.  Desain  Jaringan  Pendidikan  Teori  Graf.  Jember:  Universitas Jember
Waluyo,  E.,  Wahab,  A.  A.,  &  Rudi,  M.  (2023).  Pewarnaan  Graceful  Pada Graf Hasil Operasi Comb Graf Siklus Dan Graf Star. Kadikma , 14 (1), 9- 19.
Waluyo,  E.,  Wisudaningsih,  E.  T.,  &  Masruro,  M.  (2023).  Bilangan Kromatik  Graceful  Pada  Subdivisi  Graf  Siklus  Comb  Graf Star. Kadikma , 14 (1), 20-29.
X.  Liu  and  P.  Lu,  “Spectra  of  subdivision -vertex  and  subdivision-edge neighbourhood coronae,” Linear Algebra and Its Applications, vol. 438, no. 8, pp. 3547 – 3559, 2013.