2018/04/10 by Joseph Ray Clarence G. Damasco, Joseph R. C. Damasco, Dirk Frettlöh +2
Computer Science · Engineering · Mathematics · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #graph theory and CDMA systems #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.1804.03552
12 pages, 5 figures. Slightly improved version (typos, formulations)
openalex publication_date 2018/04/10 · arxiv created 2019/06/14 · arxiv updated 2019/06/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A vertex colouring of some graph is called perfect if each vertex of colour i has exactly aij neighbours of colour j. Being perfect imposes several restrictions on the colour incidence matrix (aij). We list several (old and new) necessary conditions for a matrix to be the colour incidence matrix of a perfect colouring. Moreover we show that a certain combination of these conditions is also sufficient. Using this we determine a list of all colour incidence matrices corresponding to perfect colourings of 3-regular, 4-regular and 5-regular graphs with two, three and four colours, respectively. As an application we determine all perfect colourings of the edge graphs of the Platonic solids with two, three and four colours, respectively.