On Indicated Coloring of Some Classes of Graphs.

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 χ i (G) . In this paper, we obtain structural characterization of { P 5 , K 4 , K i t e , B u l l } -free graphs and connected { P 6 , C 5 , K 1 , 3 } -free graphs that contain an induced C 6 . Also, we prove that { P 5 , K 4 , K i t e , B u l l } -free graphs and connected { P 6 , C 5 , P 5 ¯ , K 1 , 3 } -free graphs which contain an induced C 6 are k-indicated colorable for all k ≥ χ (G) . In addition, we show that, if m ≥ 1 and G is a bipartite graph, then χ i (K [ G ] (m , m , ... , m)) = χ (K [ G ] (m , m , ... , m)) . Further, we show that K [ C 5 ] is k-indicated colorable for all k ≥ χ (G) and as a consequence, we exhibit that { P 2 ∪ P 3 , C 4 } -free graphs, { P 5 , C 4 } -free graphs are k-indicated colorable for all k ≥ χ (G) . This partially answers one of the questions which was raised by Grzesik (Discret Math 312:3467–3472, 2012). [ABSTRACT FROM AUTHOR]