On characterizing radio kk-coloring problem by path covering problem

Let GG be a finite simple graph. For an integer k≥1k≥1, a radio kk-coloring of GG is an assignment ff of non-negative integers to the vertices of GG satisfying the condition ∣f(u)−f(v)∣≥k+1−d(u,v)∣f(u)−f(v)∣≥k+1−d(u,v) for any two distinct vertices uu, vv of GG. The span of ff is the largest integer assigned to a vertex of GG by ff and radio kk-chromatic number of GG, denoted by rck(G)rck(G), is the minimum span over all radio kk-colorings of GG. For k=2k=2, the radio kk-coloring becomes L(2,1)L(2,1) coloring problem. On the other hand, path covering problem deals with finding minimum number of vertex disjoint paths required to exhaust all the vertices of GG. Georges et al. (1994) explored an elegant relation between L(2,1)L(2,1)-coloring problem and path covering problem. As an extension of their work, we characterize the radio kk-coloring problem for any k≥2k≥2 of a graph GG by the path covering problem of GcGc, where either GG is triangle free or there is a Hamiltonian path in each component of GcGc. As an application, for any such graph, if the exact value or an upper bound is known for any rcp(G)rcp(G), p≥2p≥2, we can get the exact value or an upper bound of rck(G)rck(G) for all k≥2k≥2. Determination of radio kk-chromatic numbers of complete multi-partite graphs, a certain family of circulant graphs and join of circulant graphs of a certain family are among some other applications.