Dirk Frettlöh: Perfect colourings of simplices and hypercubes in dimension four and five with few colours, 191-201

Abstract:

A vertex colouring of some graph is called perfect if each vertex of colour $i$ has the same number $a_{ij}$ of neighbours of colour $j$. Here we determine all perfect colourings of the edge graphs of the hypercube in dimensions 4 and 5 by two and three colours, respectively. For comparison we list all perfect colourings of the edge graphs of the simplex in dimensions 4 and 5, respectively.

Key Words: Graph colouring.

2020 Mathematics Subject Classification: Primary 05C15; Secondary 05C50.

Download the paper in pdf format here.