= Solution
For a proper three-<graph colouring> $c$, associate the colors with the three <roots of unity> $d(i)=\exp(2\pi i(c(i)-1)/3)$, viewed as <unit vectors> in $\mathbb R^2$. Define $U_{ij}=2\langle d(i),d(j)\rangle$ using the real <inner product>.
This is twice a <Gram matrix>, so it is a <positive semidefinite matrix>. Its diagonal is $2$. On every <edge>, the endpoint colors differ, so their <vectors> make angle $2\pi/3$ or $4\pi/3$ and $U_{ij}=2\cos(2\pi/3)=-1$. Thus $t=3$ and this $U$ are feasible in the second <semidefinite program>, proving
$$
\boxed{\bar\vartheta(G)\leq3.}
$$
This is the <regular simplex> construction of a <strict vector coloring>.
Back to article page
