In this paper we study the existence of homomorphisms @math using semidefinite programming. Specifically, we use the vector chromatic number of a graph, defined as the smallest real number @math for which there exists an assignment of unit vectors @math to its vertices such that @math when @math . Our approach allows to reprove, without using the Erdős-Ko-Rado Theorem, that for @math the Kneser graph @math and the @math -Kneser graph @math are cores, and furthermore, that for @math there exists a homomorphism @math if and only if @math divides @math . In terms of new applications, we show that the even-weight component of the distance @math -graph of the @math -cube @math 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 @math when @math . 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 and found that at least 84 are cores.
@cite_11: This paper is the first part of an introduction to the subject of graph homomorphism in the mixed form of a course and a survey. We give the basic definitions, examples and uses of graph homomorphisms and mention some results that consider the structure and some parameters of the graphs involved. We discuss vertex-transitive graphs and Cayley graphs and their rather fundamental role in some aspects of graph homomorphisms. Graph colourings are then explored as homomorphisms, followed by a discussion of various graph products.
For an arbitrary graph @math , the is the vertex minimal subgraph to which @math admits a homomorphism. Every graph has a unique core, and the core of @math is itself a core. Moreover, @math and @math have the same core if and only if they are , i.e., @math and @math . Cores are the unique minimal elements of these homomorphic equivalence classes. In this sense, the core of a graph is the smallest graph retaining all of its homomorphic information. In we show that if @math is UVC, and its unique optimal vector coloring is injective on its vertex neighborhoods, then @math is a core (Theorem ). To illustrate the usefulness of our sufficient condition, we given an easy proof of the fact that for @math , both @math and @math are cores. This is well-known @cite_11 , but our proof avoids invoking the Erd o s-Ko-Rado Theorem to describe the structure of the maximum independent sets of these graphs, and it also avoids using the No Homomorphism Lemma. As a second application, we also show that the graphs @math constructed in are cores.