A Polynomial Time Algorithm for Minimal Roman Coloring of a Graph
Jyothi V · International Journal for Research in Applied Science and Engineering Technology · 2020
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.