Vector coloring
= Vector coloring
A vector $k$-coloring, for $k>1$, assigns a <unit vector> $v_i$ to each <vertex> of a <graph>, such that $\langle v_i,v_j\rangle\leq-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.