
arXiv: 1605.06172
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.
Coloring of graphs and hypergraphs, induced ver tex anti Ramsey number, vertex coloring, 05C15, 05C55, FOS: Mathematics, Generalized Ramsey theory, Mathematics - Combinatorics, Combinatorics (math.CO), unavoidable totally multicolored induced copy of a graph, avoidable totally multicolored induced subgraphs
Coloring of graphs and hypergraphs, induced ver tex anti Ramsey number, vertex coloring, 05C15, 05C55, FOS: Mathematics, Generalized Ramsey theory, Mathematics - Combinatorics, Combinatorics (math.CO), unavoidable totally multicolored induced copy of a graph, avoidable totally multicolored induced subgraphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
