## 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