\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Maria Axenovich and Ryan Martin}
%
%
\medskip
\noindent
%
%
{\bf Avoiding Rainbow Induced Subgraphs in Vertex-Colorings}
%
%
\vskip 5mm
\noindent
%
%
%
%
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\not\!\!\longrightarrow 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.

\bye