Game Chromatic Number of Shackle Graphs

Firmansyah Firmansyah; Abdul Mujib

doi:10.31764/jtam.v5i2.4464

Game Chromatic Number of Shackle Graphs

Firmansyah Firmansyah, Abdul Mujib

Abstract

Coloring vertices on graph is one of the topics of discrete mathematics that are still developing until now. Exploration Coloring vertices develops in the form of a game known as a coloring game. Let G graph. The smallest number k such that the graph G can be colored in a coloring game is called game chromatic number. Notated as χ_g (G). The main objective of this research is to prove game chromatic numbers from graphsThis study examines and proves game chromatic numbers from graphs shack(K_n,v_i,t),shack(S_n,v_i,t), and shack(K_(n,n),v_i,t). The research method used in this research is qualitative. The result show that χ_g (shack(K_n,v_i,t))=n,and χ_g (shack(S_n,v_i,t))=χ_g (shack(K_(n,n),v_i,t))=3. The game chromatic number of the shackle graph depends on the subgraph and linkage vertices. Therefore, it is necessary to make sure the vertex linkage is colored first.

Keywords

Game chromatics number; Vertices coloring game; Shackle graph.

Full Text:

DOWNLOAD [PDF]

References

Bartnicki, T., Breˇsar, B., Grytczuk, J., Kovˇse, M., Miechowicz, Z., & Peterin, I. (2008). Game chromatic number of Cartesian product graphs. The Electronic Journal of Combinatorics, 15(1), 1–13.

Bodlaender, H. L. (1991). On the complexity of some coloring games. International Journal of Foundations of Computer Science, 2(02), 133–147.

Bohman, T., Frieze, A., & Sudakov, B. (2019). The game chromatic number of random hypergraphs. Random Structures and Algorithms, 32(2), 223–235. https://doi.org/10.1002/rsa.20179

Chierichetti, F., Kleinberg, J., & Panconesi, A. (2012). How to schedule a cascade in an arbitrary graph. Proceedings of the ACM Conference on Electronic Commerce, 1(212), 355–368. https://doi.org/10.1145/2229012.2229040

Diana, E. L., Suryaningtyas, W., & Suprapti, E. (2016). Pengaturan Lampu Lalu Lintas di persimpangan jalan Ahmad Yani Giant dengan Aplikasi Pewarnaan Teori Graf. MUST: Journal of Mathematics Education, Science and Technology, 1(1), 69–85.

Dunn, C., Larsen, V., Lindke, K., Retter, T., & Toci, D. (2015). The game chromatic number of trees and forests. Discrete Mathematics and Theoretical Computer Science, 17(2), 31–48.

Firmansyah, & Mujib, A. (2013). Bilangan Kromatik Graf Kaktus. Seminar Nasional Matematika Dan Terapan (SiManTap 3) UniMus Bireun NAD. Bireun.

Firmansyah, & Mujib, A. (2021). Characteristics of Shackle Graph: Shack(K_n,v_((j,i) ),t), Shack(S_n,v_((j,i) ),t), & Shack(K_((n,n) ),v_((r_j,1) ),t). AXIOM : Jurnal Pendidikan Dan Matematika, 10(1), 62–71.

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

Heckel, A. (2014). The chromatic number of dense random graphs. Random Structures and Algorithms, 27(1), 140–182. https://doi.org/10.1002/rsa.20757

Maarif, S. (2017). Aplikasi Pewarnaan Titik pada Graph dalam Pembuatan Jadwal Pelajaran. Pi: Mathematics Education Journal, 1(1), 22–26.

Maryati, T. K., Salman, A. N. M., Baskoro, E. T., Ryan, J., & Miller, M. (2010a). On H-supermagic labelings for certain shackles and amalgamations of a connected graph. Utilitas Mathematica, 83(November), 333–342.

Maryati, T. K., Salman, A. N. M., Baskoro, E. T., Ryan, J., & Miller, M. (2010b). On H-supermagic labelings for certain shackles and amalgamations of a connected graph. Utilitas Mathematica, 83(October 2016), 333–342.

Mujib, A. (2019). Bilangan Kromatik Permainan Graf Pot Bunga (C_m S_n) dan Graf Pohon Palem (C_k P_l S_m). TEOREMA : Teori Dan Riset Matematika, 4(1), 13–22.

Mujib, A., & Assiyatun, H. (2011). Game Chromatic Numbers of Tensor Product Graphs. Interior, 1–8. Medan.

Mycielski, J. (1992). Games with perfect information. Handbook of Game Theory with Economic Applications, 1, 41–70.

Paulsen, V. I., & Todorov, I. G. (2015). Quantum chromatic numbers via operator systems. Quarterly Journal of Mathematics, 66(2), 677–692. https://doi.org/10.1093/qmath/hav004

Saifudin, I. (2020). Power Domination Number On Shackle Operation with Points as Lingkage. JTAM | Jurnal Teori Dan Aplikasi Matematika, 4(1), 1. https://doi.org/10.31764/jtam.v4i1.1579

Umilasari, R., Susilowati, L., & Slamin. (2020). Local irregularity chromatic number of vertex shackle product of graphs. IOP Conference Series: Materials Science and Engineering, 821(1). https://doi.org/10.1088/1757-899X/821/1/012038

Xuding, Z. (1999). the Game Coloring Number of Planar Graphs. Journal of Combinatorial Theory. Series B, 75(2), 245–258.

Zhu, X. (2000). The game coloring number of pseudo partial k-trees. Discrete Mathematics, 215(1–3), 245–262.

DOI: https://doi.org/10.31764/jtam.v5i2.4464