On indicated coloring of lexicographic product of graphs

Abstract

Indicated coloring is a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $G$ (regardless of Ben's strategy) is called the indicated chromatic number of $G$, denoted by ${\chi }_i(G)$. In this paper, we have shown that for any graphs $G$ and $H$, $G[H]$ is $k$-indicated colorable for all $k\ge \mathrm{col}(G)\mathrm{col}(H)$. Also, we have shown that for any graph $G$ and for some classes of graphs $H$ with $\chi (H)={\chi }_i(H)=\ell$, $G[H]$ is $k$-indicated colorable if and only if $G[K_{\ell }]$ is $k$-indicated colorable. As a consequence of this result we have shown that for some particular families of graphs $G$ and $H$, $G[H]$ is $k$-indicated colorable for every $k\ge \chi (G[H])$. This serves as a partial answer to one of the questions raised by A. Grzesik in \cite{and}. In addition, if $G$ is a Bipartite graph or a $\{P_5,K_3\}$-free graph (or) a $\{P_5,Paw\}$-free graph and if $H$ is from the same families of graphs, then we have shown that ${\chi }_i(G[H])=\chi (G[H])$.