Graph homomorphisms via vector colorings

In this paper we study the existence of homomorphisms $G\to H$ using semidefinite programming. Specifically, we use the vector chromatic number of a graph, defined as the smallest real number $t\ge 2$ for which there exists an assignment of unit vectors $i\mapsto p_i$ to its vertices such that $〈p_i,p_j〉\le -1∕(t-1),$ when $i\sim j$. Our approach allows to reprove, without using the Erdős–Ko–Rado Theorem, that for $n>2r$ the Kneser graph $K_{n:r}$ and the $q$-Kneser graph $q{K}_{n:r}$ are cores, and furthermore, that for $n∕r=n^{\prime }∕r^{\prime }$ there exists a homomorphism $K_{n:r}\to K_{n^{\prime }:r^{\prime }}$ if and only if $n$ divides $n^{\prime }$. In terms of new applications, we show that the even-weight component of the distance $k$-graph of the $n$-cube $H_{n,k}$ is a core and also, that non-bipartite Taylor graphs are cores. Additionally, we give a necessary and sufficient condition for the existence of homomorphisms $H_{n,k}\to H_{n^{\prime },k^{\prime }}$ when $n∕k=n^{\prime }∕k^{\prime }$. Lastly, we show that if a 2-walk-regular graph (which is non-bipartite and not complete multipartite) has a unique optimal vector coloring, it is a core. Based on this sufficient condition we conducted a computational study on Ted Spence’s list of strongly regular graphs (http://www.maths.gla.ac.uk/ es/srgraphs.php) and found that at least 84% are cores.