  We explore the concept of a graph homomorphism through the lens of
C$^*$-algebras and operator systems. We start by studying the various notions
of a quantum graph homomorphism and examine how they are related to each other.
We then define and study a C$^*$-algebra that encodes all the information about
these homomorphisms and establish a connection between computational complexity
and the representation of these algebras. We use this C$^*$-algebra to define a
new quantum chromatic number and establish some basic properties of this
number. We then suggest a way of studying these quantum graph homomorphisms
using certain completely positive maps and describe their structure. Finally,
we use these completely positive maps to define the notion of a "quantum" core
of a graph.
