AVOIDING RAINBOW INDUCED SUBGRAPHS IN VERTEX-COLORINGS

Abstract. For a fixed graph H on k vertices, and a graph G on at least k vertices, we write G − → H if in any vertex-coloring of G with k colors, there is an induced subgraph isomorphic to H whose vertices have distinct colors. In other words, if G − → H then a totally multicolored induced copy of H is unavoidable in any vertex-coloring of G with k colors. In this paper, we show that, with a few notable exceptions, for any graph H on k vertices and for any graph G which is not isomorphic to H, G �− → H. We explicitly describe all exceptional cases. This determines the induced vertex-anti-Ramsey number for all graphs and shows that totally multicolored induced subgraphs are, in most cases, easily avoidable. 1