Upper bound for radio -chromatic number of graphs in connection with partition of vertex set

Abstract

For a simple connected graph and a positive integer with , a radio -coloring of is a mapping such that holds for each pair of distinct vertices and of , where is the diameter of and is the distance between and in . The span of a radio -coloring is the number . The main aim of the radio -coloring problem is to determine the minimum span of a radio -coloring of , denoted by . Due to NP-hardness of this problem, people are finding lower bounds for for particular families of graphs or general graphs . In this article, we concentrate on finding upper bounds of radio -chromatic number for general graphs and in consequence a coloring scheme depending on a partition of the vertex set . We apply these bounds to cycle graph and hypercube and show that it is sharp when is close to the diameter of these graphs.

Keywords

• channel assignment problem
• radio -coloring
• radio -chromatic number
• span