Graph homomorphisms via vector colorings

• Main Authors: Godsil, Chris, Roberson, David E., Rooney, Brendan, Šámal, Robert, Varvitsiotis, Antonios
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Article
• 語言: English
• 出版: 2020
• 主題: Science::Mathematics
• 在線閱讀: https://hdl.handle.net/10356/143053
• 機構: 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...