KAIST Discrete Math Seminar

A k-colouring of a graph G is a partition of V(G) into k independent sets. The chromatic number χ(G) is defined as the smallest k so that G has a k-colouring. Alternatively, we can view colourings as homomorphisms to complete graphs, and define χ(G) to be the smallest k so that there is a homomorphism from G to K_k. The variants of χ(G) (for example, fractional chromatic number) are defined by replacing the complete graph K_k with a representative of a different class of graphs (for example, Kneser graphs).

In this talk, we will consider the vector chromatic number of a graph. A vector colouring of a G is a map from V(G) to vectors in R^m (for some m). The goal is to map adjacent vertices to vectors that are far apart. We will look at representations of a graph on its least eigenspace as examples of vector colourings. For distance-regular graphs, these colourings are optimal. Furthermore, we give a method for determining if these colourings are unique. This leads to proofs that certain classes of distance-regular graphs are all cores.