Perfect colourings of simplices and hypercubes in dimension four and five with few colours

2024/02/28 by Frettlöh, Dirk
#05C15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2402.18457

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.

Related

• Perfect colourings of regular graphs
• Counting perfect colourings of plane regular tilings
• Colour-bias perfect matchings in hypergraphs
• Colouring t-perfect graphs
• Regular colouring defect of a cubic graph and the conjectures of Fan-Raspaud and Fulkerson