Matrix Parameters and Perfect 3-Colorings of Symmetric Cubic Graphs

Source abstract

A graph $G$ is said to be perfectly $m$-colorable if its vertex set can be partitioned into $m$ subsets $V_1, V_2, \ldots, V_m$, such that the number of neighbors of a vertex in $V_i$ within any subset $V_j$ is constant and depends only on $i$ and $j$. This constant is denoted as $a_{ij}$, and the corresponding $m \times m$ matrix $A = (a_{ij})$ is called the parameter matrix of the graph. In this paper, we classify all possible parameter matrices for perfect $3$-colorings in cubic graphs and explore key properties of perfectly colorable cubic graphs. Additionally, we determine the parameter matrices for several well-known cubic graphs.