Perfect 4-Colorings of the 3-Regular Graphs of Order 10

Document Type : Research Paper


1 Department of Mathematics, Karaj Branch, Islamic Azad University, Karaj, Iran

2 Iran University of Science and Technology


The perfect m-coloring with matrix A = [aij ]i,j∈{1,...,m} of a graph G = (V, E) with {1, . . . , m} color is a vertices coloring of G with m-color so that number of vertex in color j adjacent to a fixed vertex in color i is aij , independent of the choice of vertex in color i. The matrix A = [aij ]i,j∈{1,...,m} is called the parameter matrix.
We study the perfect 4-colorings of the 3-regular graphs of order 10, that is, we determine a list of all color parameter matrices corresponding to perfect colorings of 3-regular graphs of order 10. 


  1. M. Alaeiyan, H. Karami, Perfect 2-colorings of the generalized Petersen graph, Proceedings Mathematical Sciences, 126, 1-6 (2016).
  2. M. Alaeiyan and A. Mehrabani, Perfect 3-colorings of cubic graphs of order 10, Electronic Journal of Graph Theory and Applications (EJGTA), 5, 194-206 (2017).
  3. S. V. Avgustinovich, I. Yu. Mogilnykh, Perfect 2-colorings of Johnson graphs J(6,3) and J(7,3), Lecture Notes in Computer Science, 5228, 11-19 (2008).
  4. S. V. Avgustinovich, I. Yu. Mogilnykh, Perfect colorings of the Johnson graphs J(8,3) and J(8,4) with two colors, Journal of Applied and Industrial Mathematics, 5, 19-30 (2011).
  5. D. G. Fon-Der-Flaass,A bound on correlation immunity, Siberian Electronic Mathematical Reports Journal, 4, 133-135 (2007).
  6. D. G. Fon-Der-Flaass, Perfect 2-colorings of a hypercube, Siberian Mathematical Journal, 4, 923-930 (2007).
  7. D. G. Fon-der-Flaass, Perfect 2-colorings of a 12-dimensional Cube that achieve a bound of correlation immunity, Siberian Mathematical Journal, 4, 292-295 (2007).
  8. A. L. Gavrilyuk and S.V. Goryainov, On perfect 2-colorings of Johnson graphs J(v,3), Journal of Combinatorial Designs, 21, 232-252 (2013).
  9. C. Godsil, Compact graphs and equitable partitions, Linear Algebra and Its Application, 255, 259-266 (1997).
  10. Z. Vahedi, M. Alaeiyan and M. Maghasedi, Perfect 4-colorings of the 3-regular graphs of order at most 8, Journal of Mathhematical Extension, Accepted (2021).