DETERMINING THE CHROMATIC NUMBER OF A MODIFIED ADENOVIRUS GRAPH USING GREEDY ALGORITHM
DOI:
https://doi.org/10.31258/jomso.v2i2.41Keywords:
Vertex coloring, chromatic number, modified adenovirus graph, greedy algorithmAbstract
One of the vertex colorings that is a well-known research topic is chromatic number which requires that any two adjacent vertices have different colors. Adenovirus is a DNA virus that causes infections in the upper or lower respiratory tract, pharynx, gastrointestinal tract, and conjunctiva. Let be the modified adenovirus graph. This graph is constructed from molecular biology data, where represents a set of vertices that represented the elements such as virus DNA genes, DNA segments, and their variants, while is the set of edges that describe overlapping interactions between segments or conflicts among them. This article discusses vertex coloring on the modified adenovirus graph using greedy. The chromatic number is the minimum number of colors used to solve the vertex coloring problem on the graph and is denoted by . This study aims to construct the graph and determine the chromatic number of the graph using the greedy algorithm. The results show that greedy algorithm give the chromatic number for the modified adenovirus graph with for even n is .
References
Al-Mujahid, M. M., 2020, Implementasi graf euler pada segmentasi gambar. Matematika Diskrit, Bandung.
Arifin M. A., 2020, Penerapan algoritma greedy pada pewarnaan graf beserta aplikasinya, Matematika Diskrit, Bandung.
Chartrand, G., Lesniak, L., and Zhang, P., 2011, Introduction to Graph Theory, Fifth Edition, New York: Taylor and Francis Group, LCC.
David, G., 2017, Introduction to Combinatorics and Graph Theory, California, USA.
Deo, N., 1974, Graph Theory: with Applications to Engineering and Computer Science, Mineola, New York: Prentice-Hall.
Diestel, R., 2024, Graph Theory, Six Edition, Germany: Springer.
Gallardo, J., Illana, M. P., Gonzalez, N. M., and Martin, C. S., 2021, Adenovirus structure: what is new?. International Journal of Molecular Sciences, Volume : 22, no. 10, 5240, pp 1-16. https://doi.org/10.3390/ijms22105240.
Gross, L. J., Yellen, J., and Anderson, M., 2019, Graph Theory and Its Applications, Third Edition, New York: Taylor and Francis Group, LLC.
Hasmawati., 2013, Dekomposisi graf hasil kali tiga lintasan ke dalam sub graf perentang reguler, Jurnal Matematika, Statistika dan Komputasi, Volume : 10, no. 1, pp 14-25. https://doi.org/10.20956/jmsk.v10i1.3408.
Irwanto, J., and Dafik., 2014. Pewarnaan titik pada graf spesial dan operasinya. Prosiding Seminar Matematika dan Pendidikan Matematik. Volume : 1, no. 5, pp 196-201. Jember, 19 November 2014. https://jurnal.unej.ac.id/index.php/psmp/article/view/930.
Kralev, V., and Kraleva, R., 2023, An analysis between different algorithms for the graph vertex coloring problem, International Journal of Electrical and Computer Engineering (IJECE), Volume : 13, no. 3, pp 2972-2980. http://doi.org/10.11591/ijece.v13i3.pp2972-2980.
Kulanayake, S., and Tikoo, S. K., 2021, Adenovirus core proteins: structure and function, Viruses, Volume : 13, no. 3, 388, pp 1-16. https://doi.org/10.3390/v13030388.
Lynch, J. P., Fishbein, M., and Echavarria, M., Adenovirus, 2011, Seminars in Respiratory and Critical Care Medicine, Volume : 32, no. 4, pp 494-511. DOI: 10.1055/s-0031-1283287.
Malaguti, E., and Toth, P., 2010, A survey on vertex coloring problems, International Transactions in Operational Research, Volume : 17, pp 1-34. DOI: 10.1111/j.1475-3995.2009.00696.x.
Munir, R., 2016, Matematika Diskrit, Edisi 3. Bandung: Informatika Bandung.
Namooltree, J., and Wetweerapong, J., 2015, Solving vertex graph coloring by heuristic methods. Proceedings of the 20th Annual Meeting in Mathematics (AMM2015). Pp 376-381. Nakhon Pathom, 27-29 Mei 2015.
Noor, C. A. P., Mamonto, K. A., and Pranata, W. E., 2019, Bilangan terhubung pelangi pada amalgamasi graf berlian, EULER: Jurnal Matematika, Sains dan Teknologi, Volume : 7, no. 1, pp 1-5. https://doi.org/10.34312/euler.v7i1.10327.
Putra, F. D., Rakhmawati, F., and Cipta, H., 2021, Penentuan rute transportasi kendaraan umum kota medan dengan menggunakan nearest neighbor method dan closed insertion method, Zeta-Math Journal. Volume : 6, no. 2, pp 1-10. https://doi.org/10.31102/zeta.2021.6.2.6-10.
Retnoningsih, I. I., Dafik,, and Hussen, S., 2022, Pewarnaan titik pada keluarga graf sentripetal, Journal of Mathematics and Applications. Volume : 3, no. 1. https://doi.org/10.25037/cgantjma.v3i1.75.
Sam, M. and Yuliani., 2016, Penerapan algoritma prim untuk membangun pohon merentang minimum (minimum spanning tree) dalam pengoptimalan jaringan transmisi nasional sulawesi selatan, Jurnal Dinamika. Volume : 7, no. 1, pp 50-61.
Sipayung, T. N., Suwilo, S., Gultom, P., and Mardiningsih., 2022, Implementation of the greedy algorithm on graph coloring, Journal of Physics: Conference Series, Volume : 2157, no. 1, pp 1-5. doi:10.1088/1742-6596/2157/1/012003.
Utari, R. H., Yulianti, L., and Sy, S., 2019, Penentuan rainbow connection number untuk amalgamasi graf lengkap dengan graf roda, Jurnal matematika UNAND, Volume : 8, no. 1, pp 345-347.
West, D. B., 2001, Introduction to Graph Theory, Second Edition, Urbana: Person Education.
