Brendan Rooney, Colourings, Vector Colourings and Cores

Colourings, Vector Colourings and Cores
Brendan Rooney
Department of Mathematical Sciences, KAIST
2015/10/28 Wed 5PM-6PM

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 Kk. The variants of χ(G) (for example, fractional chromatic number) are defined by replacing the complete graph Kk 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 Rm (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.


Comments are closed.