The Roman coloring of a graph, ࡳ which is an assignment of three colors {0, 1, 2} to the vertices of G such that any
vertex with color, 0 must be adjacent to a vertex with color, 2. It was introduced Suresh Kumar [1] motivated from ancient
Roman military strategy. The weight of a Roman coloring is defined as the sum of all the vertex colors. A Roman coloring of G
with the minimal weight is called a minimal Roman coloring of G. In this Paper, we present a polynomial time algorithm for
finding a minimal Roman coloring for a graph.