Given a graph H, let g(n,H) denote the smallest k for which the following holds. We can assign a k-colouring fv of the edge set of Kn to each vertex v in Kn with the property that for any copy T of H in Kn, there is some u∈V(T) such that every edge in T has a different colour in fu. The study of this function was initiated by Alon and Ben-Eliezer. They characterized the family of graphs H for which g(n,H) is bounded and asked whether it is true that for every other graph g(n,H) is polynomial. We show that this is not the case and characterize the family of connected graphs H for which g(n,H) grows polynomially. Answering another question of theirs, we also prove that for every ε>0, there is some r=r(ε) such that g(n,Kr)≥n1−ε for all sufficiently large n. Finally, we show that the above problem is connected to the Erdős–Gyárfás function in Ramsey Theory, and prove a family of special cases of a conjecture of Conlon, Fox, Lee and Sudakov by showing that for each fixed r the complete r-uniform hypergraph Kn(r) can be edge-coloured using a subpolynomial number of colours in such a way that at least r colours appear among any r+1 vertices.