TY - JOUR

T1 - Game chromatic number of strong product graphs

AU - Enomoto, Hikoe

AU - Fujisawa, Jun

AU - Matsumoto, Naoki

N1 - Funding Information:
Supported by JSPS Grant-in-Aid for Scientific Research (C) 20K03723.Supported by JSPS Grant-in-Aid for Early-Career Scientists 19K14583.
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2023/1

Y1 - 2023/1

N2 - The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.

AB - The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.

KW - Game chromatic number

KW - King's graph

KW - Strong product

UR - http://www.scopus.com/inward/record.url?scp=85139241436&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85139241436&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2022.113162

DO - 10.1016/j.disc.2022.113162

M3 - Article

AN - SCOPUS:85139241436

SN - 0012-365X

VL - 346

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

M1 - 113162

ER -