Avoiding rainbow induced subgraphs in vertex-colorings

Maria Axenovich ; Ryan Martin

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

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.

Détail

DOI : 10.37236/736

Classification : 05C15, 05C55
Mots-clés : unavoidable totally multicolored induced copy of a graph, induced ver tex anti Ramsey number, vertex coloring, avoidable totally multicolored induced subgraphs