Skip to main content
MathOverflow

Return to Question

Bumped by Community user
added 15 characters in body
Source Link
GMB
GMB
  • 1.4k
  • 9
  • 17

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 edgenode $(u, v) \in G$$v$, the neighborhood of $v$ is rainbow -- that is, for any two nodes $x, y$ adjacent to $v$, the two colors of $u$$x$ are different from the two colors of $v$$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?

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 edge $(u, v) \in G$, the two colors of $u$ are different from the two colors of $v$.

What is the maximum number of edges $G$ might have (up to constant factors -- big O is fine)? Have these graphs been studied before?

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?

Source Link
GMB
GMB
  • 1.4k
  • 9
  • 17

Maximum density of a double-node-colored graph

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 edge $(u, v) \in G$, the two colors of $u$ are different from the two colors of $v$.

What is the maximum number of edges $G$ might have (up to constant factors -- big O is fine)? Have these graphs been studied before?