Indicated coloring of some families of graphs.

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 χi(G).In this paper, we observe that the Nordhaus–Gaddum inequalities for the chromatic number are also satisfied by the indicated chromatic number. Further, we prove that outerplanar graphs, 3-colorable maximal planar graphs with col(G)≠5, uniquely 4-colorable planar graphs and Mn (obtained from Cn by joining diagonally opposite vertices) are k-indicated colorable for all k greater than or equal to its chromatic number. Also, we show that Ben wins the game with 4 colors when Ann uses any connected strategy on M4t+1 for any t ≥ 2. This turns out to be a generalization of the result due to Grzesik in [Indicated coloring of graphs, <italic>Discrete Math.</italic> <bold>312</bold>(23) (2012) 3467–3472]. Finally, we prove that Mycielskian of G is (k + 1)-indicated colorable when G is k-indicated colorable for some k ≥ χi(G). These partially answer one of the questions which was raised by Grzesik in [Indicated coloring of graphs, <italic>Discrete Math.</italic> <bold>312</bold>(23) (2012) 3467–3472]. [ABSTRACT FROM AUTHOR]