The Game Chromatic Number of Some Families of Direct Graph Products of G`raphs

Mohammad  Reza Salmanpour; Zahid  Raza

doi:10.65463/jprm.2026589.

Authors

Mohammad Reza Salmanpour Department of Mathematics, University of Sharjah, Sharjah-27272, UAE.
Zahid Raza Department of Mathematics, University of Sharjah, Sharjah-27272, UAE.

DOI:

https://doi.org/10.65463/jprm.2026589.

Keywords:

Graph coloring; chromatic number; direct graph product

Abstract

Given a graph G, the graph coloring game is a non-cooperative two player game such that the two players take turns properly coloring the graph. Alice wins if all vertices receive a proper coloring, otherwise Bob wins. A proper coloring is a type of coloring such that no two adjacent vertices are labelled with the same color. Our object of study is the game chromatic number Xg(G) which is the least number of colors needed for Alice to have a winning strategy for some graph G. We will mainly consider the game chromatic number of the direct products of stars, cycles, complete graphs, friendship graphs and paths in this paper

Downloads

Download data is not yet available.

References

[1] R. Alagammai and V. Vijayalakshmi. Game chromatic number of lexicographic product graphs. AKCE International Journal of Graphs and Combinatorics, 12(2-3):216–220, 2015. 1

[2] R. Alagammai and V. Vijayalakshmi. Game chromatic number of lexicographic product graphs. AKCE International Journal of Graphs and Combinatorics, 12(2-3):216–220, 2015. 1

[3] R. Alagammai and V. Vijayalakshmi. The game chromatic number of corona of two graphs. AKCE International Journal of Graphs and Combinatorics, 17(3):899–904, 2020. 1

[4] T. Bartnicki, J. Grytczuk, H. A. Kierstead, and X. Zhu. The map-coloring game. The American Mathematical Monthly, 114(9):793–803, 2007. 1

[5] T. Bohman, A. Frieze, and B. Sudakov. The game chromatic number of random graphs. Random Structures & Algorithms, 32(2):223–235, 2008. 1

[6] S. A. U. H. Bokhary, T. Iqbal, and U. Ali. Game chromatic number of cartesian and corona product graphs. Journal of Algebra Combinatorics Discrete Structures and Applications, 5(3):129–136, 2018. 1

[7] S. A. U. H. Bokhary, T. Iqbal, and U. Ali. Game chromatic number of cartesian and corona product graphs. Journal of Algebra Combinatorics Discrete Structures and Applications, 5(3):129–136, 2018. 1

[8] G. Chen, R. H. Schelp, and W. E. Shreve. A new game chromatic number. European Journal of Combinatorics, 18(1):1–9, 1997. 1

[9] H. Enomoto, J. Fujisawa, and N. Matsumoto. Game chromatic number of strong product graphs. Discrete Mathematics, 346(1):113162, 2023. 1

[10] U. Faigle, W. Kern, H. Kierstead, and W. T. Trotter. On the game chromatic number of some classes of graphs. Ars combinatoria, 35:143–150, 1993. 1

[11] L. Hollom. On graphs with maximum difference between game chromatic number and chromatic number. Discrete Mathematics, 348(2):114271, 2025. 1