Abstract. For a positive integer k, a radio k-coloring of a simple connected graph
G = (V (G), E(G)) is a mapping f :V (G){0,1,2,...}such that
| f (u) - f (v )| k 1-d (u, v ) for each pair of distinct vertices u and v of G, where
d(u, v) is the distance between u and v in G. The span of a radio k-coloring f, rck(f), is
the maximum integer assigned by it to some vertex of G. The radio k-chromatic
number, rck(G) of G is min{rck(f)}, where the minimum is taken over all radio kcolorings
f of G. If k is the diameter of G, then rck(G) is known as the radio number of
G. In this paper, we propose an improved upper bound of radio k-chromatic number
for a given graph against the other which is due to Saha and Panigrahi [1]. The
computational study shows that the proposed algorithm overcomes the previous
algorithm. We introduce a polynomial algorithm (differs from the other that is due to
Liu and Zhu [2]) which determines the radio number of the path graph n P . Finally,
we propose a new integer linear programming model for the radio k-coloring problem. |
