Game Chromatic Number of Shackle Graphs

Authors

  • Firmansyah Firmansyah Mahematics Education Department, Universitas Muslim Nusantara Al-Washliyah
  • Abdul Mujib Mahematics Education Department, Universitas Muslim Nusantara Al-Washliyah

DOI:

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

Keywords:

Game chromatics number, Vertices coloring game, Shackle graph.

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.

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.

Downloads

Published

2021-10-26

Issue

Vol. 5 No. 2 (2021): October

Section

Articles

License

Authors who publish articles in JTAM (Jurnal Teori dan Aplikasi Matematika) agree to the following terms:

  1. Authors retain copyright of the article and grant the journal right of first publication with the work simultaneously licensed under a CC-BY-SA or The Creative Commons Attribution–ShareAlike License.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).