2013/05/23 by Chris Godsil, David E. Roberson, Godsil, Chris +5 · 1 citation
Computer Science · Mathematics · #05C15 #05C60 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Graph theory and applications #Limits and Structures in Graph Theory #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1305.5545
openalex publication_date 2013/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate vector chromatic number, Lovasz theta of the complement, and quantum chromatic number from the perspective of graph homomorphisms. We prove an analog of Sabidussi's theorem for each of these parameters, i.e. that for each of the parameters, the value on the Cartesian product of graphs is equal to the maximum of the values on the factors. We also prove an analog of Hedetniemi's conjecture for Lovasz theta of the complement, i.e. that its value on the categorical product of graphs is equal to the minimum of its values on the factors. We conjecture that the analogous results hold for vector and quantum chromatic number, and we prove that this is the case for some special classes of graphs.