Perfect colorings of regular graphs

DOI10.1090/CONM/764/15356MaRDI QIDQ4998739zbMATH OpenOpenAlexFDO

Authors Joseph Ray Clarence G. Damasco, Dirk Frettlöh

Publication date 9 July 2021

Published in Polytopes and Discrete Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.03552

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: A vertex colouring of some graph is called perfect if each vertex of colour $i$ has exactly $a_{ij}$ neighbours of colour $j$. Being perfect imposes several restrictions on the colour incidence matrix $(a_{ij})$. 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.

Recommendations

• Perfect colorings of vertices of the graph G(Z^2) in three colors
• Perfect 2-colorings of the Platonic graphs
• Perfect 3-colorings on 6-regular graphs of order 9
• Perfect 2-colorings of the cubic graphs of order less than or equal to 10
• Perfect 3-colorings of the Johnson graphs J(4,2), J(5,2), J(6,2) and Petersen graph.

Cites work

• Boolean degree 1 functions on some classical association schemes
• Bounding the diameter of distance. Regular graphs
• Equitable decompositions of graphs with symmetries
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 2131198 (Why is no real title available?)
• scientific article; zbMATH DE number 5379405 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 7009673 (Why is no real title available?)
• scientific article; zbMATH DE number 3224340 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• On calculation of the interweight distribution of an equitable partition
• On perfect 2-colorings of Johnson graphs \(J(v, 3)\)
• On the regularity of perfect 2-colorings of the Johnson graph
• Perfect 2-colorings of the Johnson graphs J(8,3) and J(8,4)
• Perfect 2-colorings of the Platonic graphs
• Perfect 3-colorings of the Johnson graphs J(4,2), J(5,2), J(6,2) and Petersen graph.

Cited in

(16)

• Perfect 3-colorings on 6-regular graphs of order 9
• Kaleidoscopic colorings of graphs
• Perfect colorings of the prism graph
• Reconfiguration of colorable sets in classes of perfect graphs
• Perfect colorings of vertices of the graph G(Z^2) in three colors
• Perfect 2-colorings of the Platonic graphs
• Colouring Some Classes of Perfect Graphs Robustly
• On (k,l)-chromatic edge colorings of Platonic solids
• scientific article; zbMATH DE number 1033812 (Why is no real title available?)
• On word colourings and some perfect graphs
• scientific article; zbMATH DE number 863472 (Why is no real title available?)
• Perfect 4-colorings of the 3-regular graphs of order at most 8
• Reconfiguration of Colorable Sets in Classes of Perfect Graphs
• Perfect 2-colorings of the cubic graphs of order less than or equal to 10
• On the existence of graphs which can colour every regular graph
• Perfect colourings of simplices and hypercubes in dimension four and five with few colours

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Perfect colorings of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4998739)