This problem is similar to finding the achromatic number $\psi(G)$ of a graph, and even more similar to finding the pseudoachromatic number $\Psi(G)$.
Both of these problems share the unusual property with your problem of trying to maximize the number of colors used. The achromatic number of $G$ is the maximum number of colors in a proper coloring where, for any two colors $i$ and $j$, there is an edge joining a vertex of color $i$ to a vertex of color $j$. The pseudoachromatic number of $G$ is defined similarly, except that the coloring no longer needs to be proper.
The pseudoachromatic number is most similar to the number defined in this question, except that not every vertex needs to have a neighbor in every other color class. It's enough that any two color classes have one edge between them. The pseudoachromatic number is an upper bound on the number in this question, though it's hard to say how it compares to the trivial bound of $\delta(G)+1$.
The achromatic number of a graph is defined by Harary and Hedetniemi in their paper with the obvious title, and the pseudoachromatic number in Gupta's Bounds on the chromatic and achromatic numbers of complementary graphs. One might look for any discussion of the problem in this question among the papers citing one of these two. I haven't found any, but I haven't gone to the extreme step of looking through all such papers.