Skip to main content
1 of 2
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?

GMB
  • 1.4k
  • 9
  • 17