IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Graph Homomorphisms and Vector Colorings

  • Feb. 8, 2019
  • 2:30 p.m.
  • LeConte 312

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, 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 by Karger, Motwani, and Sudan. In 2017, Godsil, et. al., 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. 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.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC