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 negated right arrow 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. |
Year | Venue | Keywords |
---|---|---|
2008 | ELECTRONIC JOURNAL OF COMBINATORICS | ramsey number |
Field | DocType | Volume |
Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Induced subgraph,Isomorphism,Rainbow,Mathematics | Journal | 15 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 5 |
PageRank | References | Authors |
0.65 | 9 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Maria Axenovich | 1 | 209 | 33.90 |
Ryan Martin | 2 | 144 | 14.43 |