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.

Download

Included in

Mathematics Commons

Share

COinS