Chromatic numbers, Sabadussi's Theorem and Hedetniemi's conjecture for non-commutative graphs

Abstract Non-commutative graph theory is an operator space generalization of graph theory. Well known graph parameters such as the independence number and Lovasz theta function were first generalized to this setting by Duan, Severini, and Winter [1] . In [11] , Stahlke introduces a generlazation of the chromatic number of a graph and obtains a Lovasz sandwich inequality for certain operator spaces. We introduce two new generalizations of the chromatic number to non-commutative graphs and provide an upper bound on the parameter of Stahlke. We provide a generalization of the graph complement and show the chromatic number of the orthogonal complement of a non-commutative graph is bounded below by its theta number. We also provide a generalization of both Sabadussi's Theorem and Hedetniemi's conjecture to non-commutative graphs.