Game Chromatic Number of Tadpole Graph, Broom Graph, and Tribune Graph

Fransiskus Fran; M Luthfi Abdurahman

doi:10.31764/jtam.v8i4.25817

Game Chromatic Number of Tadpole Graph, Broom Graph, and Tribune Graph

Fransiskus Fran, M Luthfi Abdurahman

Abstract

Graph coloring game is one of application in graph theory. The goal in this article is determine game chromatic number of tadpole graph, broom graph, and tribune graph. The graphs are simple, connected, and undirected and thus eligible for playing graph coloring game. Given two players with the first player is called A and second player is called B coloring vertex of graph G with a set of colors C={c_1,c_2,c_3, ..., c_k}. A must to make sure that all vertex of G has colored and B must try to prevent A coloring of all vertex. The first step was taken by A as first player, two players take turns coloring vertex of graph G, with rule that every vertex have different color from the neighbourhood. If all vertex of graph G have been colored, then A win or B win if some vertex hasn’t colored. The smallest number of k if A has a strategy to win at graph G with k color, then k called game chromatic number which is denoted by χ_g (G). The strategy to win this game is coloring the biggest degree of vertex in graph first. The result obtained from this paper is A win the game with the strategy of first coloring the largest degrees of vertex. So, exact of game chromatic number of tadpole graph is 3, broom graph is 2 or 3 with several conditions, and tribune graph is 3 or 4 with several conditions.

Keywords

Graph Coloring Games; Chromatic Numbers; Tadpole Graph; Broom Graph; Tribune Graph.

Full Text:

DOWNLOAD [PDF]

References

Abdurahman, M. L., Helmi, H., & Fran, F. (2024). Bilangan Kromatik Permainan Graf Ubur-Ubur, Graf Siput, dan Graf Gurita. Jambura Journal of Mathematics, 6(1). 118-124 . https://doi.org/10.37905/jjom.v6i1.23958

Akhtar, M. S., Ali, U., Abbas, G., & Batool, M. (2019). On the game chromatic number of splitting graphs of path and cycle. Theoretical Computer Science, 795, 50–56. https://doi.org/10.1016/j.tcs.2019.05.035

Anggalia, F. (2017). Penentuan Rainbow Connection Number Pada Graf Buku Segiempat, Graf Kipas, Dan Graf Tribun. Jurnal Matematika UNAND, 6(1), 153. https://doi.org/10.25077/jmu.6.1.153-160.2017

Bharadwaj, H., & Mangam, T. A. (n.d.). The total game chromatic number of paths, cycles and stars.

Bradshaw, P. (2021). Graph colorings with restricted bicolored subgraphs: II. The graph coloring game (arXiv:2008.13275). arXiv. http://arxiv.org/abs/2008.13275

Bradshaw, P., & Zeng, J. A. (2024). Paintability of $r$-chromatic graphs (arXiv:2403.11888). arXiv. http://arxiv.org/abs/2403.11888

Bravyi, S., Kliesch, A., Koenig, R., & Tang, E. (2022). Hybrid quantum-classical algorithms for approximate graph coloring. Quantum, 6, 678. https://doi.org/10.22331/q-2022-03-30-678

Budi, H. S., Dafik, Tirta, I. M., Agustin, I. H., & Kristiana, A. I. (2021). On rainbow antimagic coloring of graphs. Journal of Physics: Conference Series, 1832(1), 012016. https://doi.org/10.1088/1742-6596/1832/1/012016

Corso, G., Cavalleri, L., Beaini, D., Liò, P., & Velicˇkovic, P. (n.d.). Principal Neighbourhood Aggregation for Graph Nets.

Escoﬃer, B., Gourves, L., & Monnot, J. (n.d.). Strategic Coloring of a Graph ⋆ ⋆⋆.

Fernandez V, M., & Warnke, L. (2024). The clique chromatic number of sparse random graphs (arXiv:2403.03013). arXiv. http://arxiv.org/abs/2403.03013

Furtado, A., Dantas, S., De Figueiredo, C., & Gravier, S. (2019). On Caterpillars of Game Chromatic Number 4. Electronic Notes in Theoretical Computer Science, 346, 461–472. https://doi.org/10.1016/j.entcs.2019.08.041

Garrett, H. (2021). Different Types of Neutrosophic Chromatic Number. https://doi.org/10.20944/preprints202112.0335.v1

Inayah, N., Aribowo, W., & Windra Yahya, M. M. (2021). The Locating Chromatic Number of Book Graph. Journal of Mathematics, 2021, 1–3. https://doi.org/10.1155/2021/3716361

Jabbar, Z. L. A., Dafik, Adawiyah, R., Albirri, E. R., & Agustin, I. H. (2020). On rainbow antimagic coloring of some special graph. Journal of Physics: Conference Series, 1465(1), 012030. https://doi.org/10.1088/1742-6596/1465/1/012030

Joedo, J. C., Dafik, Kristiana, A. I., Agustin, I. H., & Nisviasari, R. (2022). On the rainbow antimagic coloring of vertex amalgamation of graphs. Journal of Physics: Conference Series, 2157(1), 012014. https://doi.org/10.1088/1742-6596/2157/1/012014

Kierstead, H. A. (2005). Asymmetric graph coloring games. Journal of Graph Theory, 48(3), 169–185. https://doi.org/10.1002/jgt.20049

Liu, L., & Ning, B. (2023). Unsolved Problems in Spectral Graph Theory. https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.04.003

Lone, A. I., & Goswami, V. (2023). Connected certified domination edge critical and stable graphs. Acta Universitatis Sapientiae, Informatica, 15(1), 25–37. https://doi.org/10.2478/ausi-2023-0003

Lu, J., Zhu, L., & Gao, W. (2023). Remarks on bipolar cubic fuzzy graphs and its chemical applications. International Journal of Mathematics and Computer in Engineering, 1(1), 1–10. https://doi.org/10.2478/ijmce-2023-0001

Maghfiro, S., Dafik, Kristiana, A. I., Nisviasari, R., Slamin, & Agustin, I. H. (2023). A Study of the Rainbow Antimagic Coloring of Double Wheel and Parachute Graphs. In Dafik (Ed.), Proceedings of the 6th International Conference on Combinatorics, Graph Theory, and Network Topology (ICCGANT 2022) (Vol. 6, pp. 120–132). Atlantis Press International BV. https://doi.org/10.2991/978-94-6463-138-8_11

Manamtam, J. A., Garciano, A. D., & Tolentino, M. A. C. (2022). Sigma chromatic numbers of the middle graph of some families of graphs. Journal of Physics: Conference Series, 2157(1), 012001. https://doi.org/10.1088/1742-6596/2157/1/012001

Matsumoto, N. (2019). The difference between game chromatic number and chromatic number of graphs. Information Processing Letters, 151, 105835. https://doi.org/10.1016/j.ipl.2019.105835

Pavithra, R., & Vijayalakshmi, D. (n.d.). On Grundy Chromatic Number For Splitting Graph On Different Graphs.

Ponraj, R., Philip, S. Y. D., & Kala, R. (2022). 4-Total Difference Cordial Labeling Of Some Special Graphs. Journal of Applied and Pure Mathematics, 4(1_2), 51–61. https://doi.org/10.23091/JAPM.2022.051

Saifudin, I., Widiyaningtyas, T., Rhomdani, R. W., & Dasuki, Moh. (2024). Domination Numbers in Graphs Resulting from Shackle Operations with Linkage of any Graph. JTAM (Jurnal Teori Dan Aplikasi Matematika), 8(2), 336. https://doi.org/10.31764/jtam.v8i2.19675

Saleh, A., Muthana, N., Al-Shammakh, W., & Alashwali, H. (2020). Monotone Chromatic Number Of Graphs.

Samli, S. B., John, J., & Chellathurai, S. R. (n.d.). The Double Geo Chromatic Number Of A Graph.

Samuel, A. E., & Vani, S. K. (2018). Prime Labeling to Brush Graphs. International Journal of Mathematics Trends and Technology, 55(4), 259–262. https://doi.org/10.14445/22315373/IJMTT-V55P533

Sriram, S., Ranganayakulu, D., Venkat, I., & Subramanian, K. G. (n.d.). On Eccentric Graphs of Broom Graphs.

Xue, H., & Li, L. (2023). Motion, Static Force, and Efficiency Analysis of Planetary Gear Transmission Based on Graph Theory. Applied Sciences, 13(19), 10983. https://doi.org/10.3390/app131910983

Yusuf, R., Mujib, A., Panjaitan, D. J., & Puspa, F. (2023). The Game Chromatic Numbers of Corona Product Graphs. 120.

DOI: https://doi.org/10.31764/jtam.v8i4.25817