On indicated coloring of some classes of graphs

Abstract

Indicated coloring is a type of game coloring 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 obtain structural characterization of connected $\{P_5,K_4,Kite,Bull\}$-free graphs which contains an induced $C_5$ and connected $\{P_6,C_5,K_{1,3}\}$-free graphs that contains an induced $C_6$. Also, we prove that $\{P_5,K_4,Kite,Bull\}$-free graphs that contains an induced $C_5$ and $\{P_6,C_5,\overline{P_5},K_{1,3}\}$-free graphs which contains an induced $C_6$ are $k$-indicated colorable for all $k\ge \chi (G)$. In addition, we show that $\mathbb{K}[C_5]$ is $k$-indicated colorable for all $k\ge \chi (G)$ and as a consequence, we exhibit that $\{P_2\cup P_3,C_4\}$-free graphs, $\{P_5,C_4\}$-free graphs are $k$-indicated colorable for all $k\ge \chi (G)$. This partially answers one of the questions which was raised by A. Grzesik in \cite{and}.

19 Pages