Document Type : Research Paper

Author

• Mehdi Alaeiyan

School of Mathematics, Iran University of Science and Technology, Narmak, Tehran 16846, Iran

Abstract

Perfect coloring is a generalization of the notion of completely regular codes, given by Delsarte. A perfect m-coloring of a graph G with m colors is a partition of the vertex set of G into m parts $A_1, . . . , A_m$ such that, for all $i, j \in \{1, . . . , m\}$, every vertex of $A_i$ is adjacent to the same number of vertices, namely, $a_{ij}$ vertices, of $A_j$. The matrix $A = (a_{ij} )$, $i, j \in \{1, 2,... , m\}$, is called the parameter matrix. We study the perfect 3-colorings (also known as the equitable partitions into three parts) of the Heawood graph. In particular, we classify all the realizable parameter matrices of perfect 3-colorings for the Haywood graphs.

Keywords

• perfect coloring
• parameter matrices
• cubic graph

20.1001.1.20086822.2021.12.1.55.0