Game chromatic number of honeycomb related networks

Imran, Muhammad; Bokhary, Syed Ahtsham Ul Haq; Akhtar, Muhammad Shahzad; Matsumoto, Naoki

doi:10.22049/cco.2023.28663.1658

تعداد نشریات	5
تعداد شماره‌ها	113
تعداد مقالات	1,293
تعداد مشاهده مقاله	1,275,367
تعداد دریافت فایل اصل مقاله	1,124,133

	Game chromatic number of honeycomb related networks
Communications in Combinatorics and Optimization
مقاله 9، دوره 9، شماره 4، اسفند 2024، صفحه 747-757 اصل مقاله (1.15 M)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2023.28663.1658
نویسندگان
Muhammad Imran^* ¹؛ Syed Ahtsham Ul Haq Bokhary²؛ Muhammad Shahzad Akhtar²؛ Naoki Matsumoto³
¹Department of Mathematical Sciences, United Arab Emirates University, P.O. Box 15551, Al Ain, United Arab Emirates
²Centre for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University, Multan, Pakistan
³Faculty of Education, University of the Ryukyus, Okinawa, Japan
چکیده
Let $G$ be a simple connected graph having finite number of vertices (nodes). Let a coloring game is played on the nodes of $G$ by two players, Alice and Bob alternately assign colors to the nodes such that the adjacent nodes receive different colors with Alice taking first turn. Bob wins the game if he is succeeded to assign k distinct colors in the neighborhood of some vertex, where k is the available number of colors. Otherwise, Alice wins. The game chromatic number of G is the minimum number of colors that are needed for Alice to win this coloring game and is denoted by $\chi_{g}(G)$. In this paper, the game chromatic number $\chi_{g}(G)$ for some interconnecting networks such as infinite honeycomb network, elementary wall of infinite height and infinite octagonal network is determined. Also, the bounds for the game chromatic number $\chi_{g}(G)$ of infinite oxide network are explored.
کلیدواژه‌ها
Coloring؛ game chromatic number (GCN)؛ infinite honeycomb network؛ infinite xxide network؛ elementary wall of infinite height

مراجع
[1] M. Ahmad, D. Afzal, W. Nazeer, and S. Kang, On topological indices of octagonal network, Far East J. Math. Sci. 102 (2017), no. 11, 2563–2571. [2] M.S. Akhtar, U. Ali, G. Abbas, and M. Batool, On the game chromatic number of splitting graphs of path and cycle, Theoret. Comput. Sci. 795 (2019), 50–56. https://doi.org/10.1016/j.tcs.2019.05.035 [3] T. Bartnicki, B. Brešar, J. Grytczuk, M. Kovše, Z. Miechowicz, and I. Peterin, Game chromatic number of Cartesian product graphs, Electron. J. Comb. 15 (2008), Articel ID: R72. https://doi.org/10.37236/796 [4] R. Belmonte, A. Giannopoulou, D. Lokshtanov, and D.M. Thilikos, The structure of $w_4$-immersion-free graphs, 2016. [5] H.L. Bodlaender, On the complexity of some coloring games, Int. J. Found. Comput. Sci. 2 (1991), no. 2, 133–147. https://doi.org/10.1142/S0129054191000091 [6] S.A.U.H. Bokhary and M.S. Akhtar, Game chromatic number of some convex polytope graphs, Util. Math. 104 (2017), 15–22. [7] S.A.U.H. Bokhary, T. Iqbal, and U. Ali, Game chromatic number of Cartesian and corona product graphs, J. Algebra Comb. Discrete Appl. 5 (2018), no. 3, 129–136. [8] J.A. Bondy and U.S.R. Murty, Graph Theory, 6 springer, Springer, New York, 2008. [9] D. Chakraborti, A. Frieze, and M. Hasabnis, The game chromatic number of a random hypergraph, pp. 153–175, Springer Cham, 2020. [10] T Dinski and X Zhu, A bound for the game chromatic number of graphs, Discrete Math 196 (1999), no. 1-3, 109–115. https://doi.org/10.1016/S0012-365X(98)00197-6 [11] H. Enomoto, J. Fujisawa, and N. Matsumoto, Game chromatic number of strong product graphs, Discrete Math. 346 (2023), no. 1, Article ID: 113162. https://doi.org/10.1016/j.disc.2022.113162 [12] U. Faigle, U. Kern, H. Kierstead, and W.T. Trotter, On the game chromatic number of some classes of graphs, Ars Combin. 35 (1993), 143–150. [13] A. Furtado, S. Dantas, C. de Figueiredo, and S. Gravier, On caterpillars of game chromatic number 4, Electron. Notes Theoret. Comput. Sci. 346 (2019), 461–472. https://doi.org/10.1016/j.entcs.2019.08.041 [14] D.J. Guan and X. Zhu, Game chromatic number of outerplanar graphs, J. Graph Theory 30 (1999), no. 1, 67–70. [15] P. Holub, M. Miller, H. Pérez-Rosés, and J. Ryan, Degree diameter problem on honeycomb networks, Discrete Appl. Math. 179 (2014), 139–151. https://doi.org/10.1016/j.dam.2014.07.012 [16] H.A. Kierstead and W.T. Trotter, Planar graph coloring with an uncooperative partner, J. Graph Theory 18 (1994), no. 6, 569–584. https://doi.org/10.1002/jgt.3190180605 [17] P.D. Manuel and I. Rajasingh, Minimum metric dimension of silicate networks., Ars Combin. 98 (2011), 501–510. [18] C. Sia and J. Gallian, The game chromatic number of some families of Cartesian product graphs, AKCE Int. J. Graphs Comb. 6 (2009), no. 2, 315–327. [19] F. Simonraj and A. George, Topological properties of few poly oxide, poly silicate, DOX and DSL networks, Int. J. Future Comput. Commun. 2 (2013), no. 2, 90–95. http://doi.org/10.7763/IJFCC.2013.V2.128 [20] X. Zhu, Game coloring the Cartesian product of graphs, J. Graph Theory 59 (2008), no. 4, 261–278. https://doi.org/10.1002/jgt.20338
آمار تعداد مشاهده مقاله: 372 تعداد دریافت فایل اصل مقاله: 1,278

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

Game chromatic number of honeycomb related networks