On subgraphs induced by transversals in vertex-partitions of graphs (Q2500955)

Summary: 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\geq 1\), we find a family \({\mathcal F}\) of at most six graphs on \(k\) vertices such that the following holds. If \(H\notin {\mathcal 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.