Let $G$ be a graph with the following properties. $C$ is a set of colors. The nodes of $G$ are $C \choose 2$. For any node $v$, the neighborhood of $v$ is rainbow -- that is, for any two nodes $x, y$ adjacent to $v$, the two colors of $x$ are different from the two colors of $y$.
What is the maximum number of edges $G$ might have (up to constant factors -- big O is fine)? Have these graphs been studied before?
[Self-Answer]
The answer is $\Theta(c^3)$. The upper bound is trivial. To construct a graph with $\Omega(c^3)$ edges, randomly add $c/100$ edges incident to each node, and say that an edge $(u, v)$ is "bad" if $v$ shares a color with another of $u$'s neighbors (or vice versa), and "good" otherwise. A simple probability calculation shows that any given edge is bad with only constant probability, so (in expectation) at most a constant fraction of the edges are bad. We can then delete all bad edges, and we obtain a graph satisfying the constraints with (in expectation) $\Omega(c^3)$ edges.
Here is an almost optimal explicit example.
It is well known that the edges of $K_c$ can be colored properly in $c-1$ colors if $c$ is even, and in $c$ colors if $c$ is odd. Now, each edge of $K_c$ is a vertex of $G$; connect it by an edge in $G$ with all edges of $K_c$ of the same color. Then the degree of each vertex is just 1 less than the potentially maximal one.
Just in case: how to color the edges. If $c$ is odd, regard the vertices as the vertices of a regular $c$-gon; the sides and diagonals parallel to each other form a color. If $c$ is even, regard the vertices as the vertices of a regular $(c-1)$-gon and its center; each color consists of one `radius' from the center, together with all sides and diagonals perpendicular to this radius.
