Homomorphisms of binary Cayley graphs

A binary Cayley graph is a Cayley graph based on a binary group. In 1992, Payan proved that any non-bipartite binary Cayley graph must contain a generalized Mycielski graph of an odd cycle, implying that such a graph cannot have chromatic number 3. We strengthen this result first by proving that any non-bipartite binary Cayley graph must contain a projective cube as a subgraph. We further conjecture that any homomorphism of a non-bipartite binary Cayley graph to a projective cube must be surjective and we prove a special case of this conjecture. (C) 2015 Elsevier B.V. All rights reserved.