3
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

1
$\begingroup$

[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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.