A Practical Algorithm for [r, s, t]-Coloring of Graph

Document Type : Research Paper


Department of mathematics, Jahrom Univertsity


Coloring graphs is one of important and frequently used topics in diverse sciences. In the majority of the articles, it is intended to find a proper bound for vertex coloring, edge coloring or total coloring in the graph. Although it is important to find a proper algorithm for graph coloring, it is hard and time-consuming too. In this paper, a new algorithm for vertex coloring, edge coloring and [r, s, t]- coloring is presented. Then, this algorithm is used to solve the applied problems of eight-queens and [r, s, t]- coloring. Here, there are numerical examples to study the efficiency of the method and to compare the results.


  1. D. Kral and R. Shrekovski, A theorem about channel assignment problem, SIAM Journal on Discrete Mathematics, 16 (3): 426–437, (2003).
  2. U. Schauz, The tournament scheduling problem with absences, European Journal of Operational Research, 254(3): 746–754, (2016).
  3. A. Kemnitz and M. Marangio, [r, s, t]-Colorings of graphs, Discrete Mathematics, 307: 199–207, (2007).
  4. N. Biggs, Algebraic Graph Theory, Cambridge Mathematical Library (2nd Ed), 2.1, p.7, Cambridge University Press, (1993).
  5. S. Skiena, Line Graph, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, 128 and 135-139, Reading, MA: Addison-Wesley (1990).
  6. E.J. Hoffman, J.C. Loessi, and R.C. Moore, Construction for the solution of the m queens problem, Mathematics Magazine, 42: 66–72, (1969).