Game Chromatic Number of Honeycomb Related Networks

Document Type : Original paper

Authors

1 Department of Mathematical Sciences, United Arab Emirates University, P.O. Box 15551, Al Ain, United Arab Emirates

2 Centre for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University, Multan, Pakistan

3 Faculty of Education, University of the Ryukyus, Okinawa, Japan

Abstract

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.

Keywords

Main Subjects

References

[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
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 25 June 2023

Files

Share

How to cite

Statistics