Avoiding rainbow induced subgraphs in vertex-colorings (Q1010717)

Summary: For a fixed graph \(H\) on \(k\) vertices, and a graph \(G\) on at least \(k\) vertices, we write \(G\longrightarrow 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\longrightarrow 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\nrightarrow 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.