Date of Award
2018
Document Type
Open Access Dissertation
Department
Mathematics
First Advisor
Linyuan Lu
Abstract
A graph vertex coloring is an assignment of labels, which are referred to as colors, such that no two adjacent vertices receive the same color. The vertex coloring problem is NP-Complete [8], and so no polynomial time algorithm is believed to exist. The notion of a graph vector coloring was introduced as an efficiently computable relaxation to the graph vertex coloring problem [7]. In [6], the authors examined the highly symmetric class of 1-walk regular graphs, characterizing when such graphs admit unique vector colorings. We present this characterization, as well as several important consequences discussed in [5, 6]. By appealing to this characterization, several important families of graphs, including Kneser graphs, Quantum Kneser graphs, and Hamming graphs, are shown to be uniquely vector colorable. Next, a relationship between locally injective vector colorings and cores is examined, providing a sufficient condition for a graph to be a core. As an immediate corollary, Kneser graphs, Quantum Kneser graphs, and Hamming graphs are shown to be cores. We conclude by presenting a characterization for the existence of a graph homomorphism between Kneser graphs having the same vector chromatic number. The necessary condition easily generalizes to Quantum Kneser graphs, simply by replacing combinatorial expressions with their quantum analogues.
Rights
© 2018, Michael Robert Levet
Recommended Citation
Robert Levet, M.(2018). Graph Homomorphisms and Vector Colorings. (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/4472