Chromatic numbers and indices of the optimised degree six 3-modified chordal ring network topology


  • S. L. E. Chien Universiti Pendidikan Sultan Idris
  • R. N. Farah Universiti Pendidikan Sultan Idris
  • M. Othman Universiti Putra Malaysia



Parallel processing, modified chordal rings, graph colouring, chromatic number, chromatic index


Graph colouring is the labelling of the elements of a graph subject to certain constraints. It is divided into vertex and edge colouring. In both cases, the assignment of labels, traditionally called colours is such that two vertices or edges must not have the same colour. This has various applications, especially in parallel computing. This paper introduces the degree six 3-modified chordal ring, CHR6o3, a parallel network interconnection topology model, and discusses its node and link colouring. Despite its asymmetry, the chromatic number of CHR6o3 cannot be generalised and must be determined specifically based on the combination of chords in each case. Cases where the chromatic index of CHR6o3 is its degree and where it is its one colour more than its degree were generalised and proven. Chromatic numbers are important in minimising the completion times of processes in parallel processing by reducing points of synchronisation, and link colouring aids processor scheduling.


K.H. Rosen. New York: McGraw-Hill (2012).

M. Van Steen (2010). Obtained from

R.N.F. Azura, M. Othman, Y.H. Peng, and M.H. Selamat. Malaysian Journal of Mathematical Sciences 4, 2 (2010) 147-157.

R.N. Farah, M. Othman, M.H. Selamat. Journal of Computer Science, 6, 3 (2010) 279-284.

S. Bujnowski, B. Dubalski, A. Zabludowski, D. Ledziński, T. Marciniak, and J.M. Pedersen. Image Processing & Communications Challenges 2, AISC, 84 (2010) 435-445.

B.W. Arden and H. Lee. IEEE Trans. Computer, C-30, 4 (1981) 291-295.

D. Ledziński, S. Bujnowski, T. Marciniak, J.M. Pedersen, J.G. Lopez. Image Processing and Communications Challenges 5, AISC 233 (2014) 281-299.

R.L. Brooks. Proc. of the Cambridge Philosophical Society, Mathematical and Physical Sciences, 37 (1941) doi:10.1017/S030500410002168X.

D. Marx. Periodica Polytechnica, Electrical Engineering 48, 1 (2004) 11-16.

P. Gupta. International Journal of Core Engineering & Management (IJCEM). 1, 2 (2014) 27-32.

D. Jungnickel. Springer (2013).

A.G. Chetwynd and A.J.W. Hilton. Proc. of the London Mathematical Society (1985) doi:10.1112/plms/s3-50.2.193.

Green, R. (2015). Obtained from