Graph homomorphisms via vector colorings

• Main Authors: Godsil, Chris, Roberson, David E., Rooney, Brendan, Šámal, Robert, Varvitsiotis, Antonios
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2020
• Subjects: Science::Mathematics
• Online Access: https://hdl.handle.net/10356/143053
• Institution: Nanyang Technological University

In this paper we study the existence of homomorphisms G→H using semidefinite programming. Specifically, we use the vector chromatic number of a graph, defined as the smallest real number t≥2 for which there exists an assignment of unit vectors i↦p i to its vertices such that 〈p i ,p j 〉≤−1∕(t−1), wh...