# Problem (proposed by Erdös and Tuza [1])

Let $$G$$ denote a given graph on $$e$$ edges. Suppose the edges of a complete graph on $$n$$ vertices are colored in $$e+1$$ colors so that at every vertex each color occurs at least $$(1-\epsilon)n/(e+1)$$ times. Is it true that there is a subgraph isomorphic to $$G$$ with all edges in different colors?

The special case when $$H$$ is a triangle is well understood. However, for other graphs, the problem remains open [1][2] even for $$d$$-regular colorings when $$n=de+1$$.

Bibliography
1 P. Erdös and Z. Tuza, Rainbow subgraphs in edge-colorings of complete graphs, quo vadis, graph theory? Ann. Discrete Math. 55, (1993), 81-88.

2 P. Erdös, Some of my favourite problems on cycles and colourings, Cycles and colourings '94 Stará Lesná, 1994, Tatra Mt. Math. Publ. 9 (1996), 7-9.