On Subgraphs Induced by Transversals in Vertex-Partitions of Graphs - Axenovich, Maria (The Electronic Journal of Combinatorics, 2006)
For a fixed graph H on k vertices, we investigate the graphs, G, such that for any partition of the vertices of G into k color classes, there is a transversal of that partition inducing H. For every integer k≥ 1, we find a family F of at most six graphs on k vertices such that the following holds. If H otin F, then for any graph G on at least 4k-1 vertices, there is a k-coloring of vertices of G avoiding totally multicolored induced subgraphs isomorphic to H. Thus, we provide a vertex-induced anti-Ramsey result, extending the induced-vertex-Ramsey theorems by Deuber, Rödl et al.