Perfect 3-coloring On 6-regular Graph Of Order 9

The coloring problem of graphs has always been a hot topic of graph theory.In this paper,we study the perfect coloring problem of graphs.The concept of perfect n-colorings of a graph is a partition of its vertex set into n parts A₁,A₂,A_m such that for all i,j?{1,...,m},each vertex of A_i is adjacent to a_ij number of vertices of A_j.The matrix A=(a_ij)_m×m is called quotient matrix or coloring adjacency matrix or parameter matrix.Perfect coloring of graphs plays an important role in many fields,such as operation research,algebraic combinatorics,coding theory and so on.In this paper,we study the perfect 3-colorings on 6-regular graphs of order 9,and give the corresponding color adjacency matrix of different 6-regular graphs of order 9.We also give an algorithm to find the adjacency matrix of all different graphs of any k-regular graphs of order 9,and combine the algorithm given in[27]to find all color adjacency matrix for a given number of colors.So that we can give a better solution to the perfect coloring problem of general regular graphs.