Avoiding rainbow induced subgraphs in edge-colorings.
Chelsea Sackett, Maria Axenovich · 2009
Let H be a fixed graph on k edges. For an edge-coloring c of H, we say that H is rainbow, or totally multicolored if c assigns distinct colors to all edges of H. We show, that it is easy to avoid rainbow induced graphs H. Specifically, we prove that for any graph H (with some notable exceptions), and for any graph G, G = H, there is an edge-coloring of G with k colors which contains no induced rainbow subgraph isomorphic to H. This demonstrates that, in a sense, induced subgraphs do not have “anti-Ramsey”-type properties.