Vector coloring

A vector $k$-coloring, for $k>1$, assigns a unit vector $v_i$ to each vertex of a graph, such that $⟨v_i,v_j⟩\le -1/(k-1)$ on every edge. A graph colouring with $k$ colors gives a vector $k$-coloring by placing the colors at the vertices of a regular simplex. The Gram matrix of these vectors allows semidefinite programming to search for such a representation.

A strict vector $k$-coloring requires equality $⟨v_i,v_j⟩=-1/(k-1)$ on every edge. The least admissible $k$ is the complement theta number for a graph with an edge. Allowing merely an inequality defines the potentially smaller vector chromatic number.

For unit vectors $u,v$ and a random normal $a$ with independent standard normal distribution coordinates,The Gaussian distribution is invariant under orthogonal transformations. Projecting onto the plane spanned by $u,v$ therefore gives a uniformly distributed direction. If the angle between $u,v$ is $\theta$, the sign-disagreement directions form two sectors of total angle $2\theta$ out of $2\pi$. The endpoint cases $u=v$ and $u=-v$ give probabilities zero and one directly.