A Linear Algorithm for Radio k-Coloring Powers of Paths Having Small Diameter

Publications

A Linear Algorithm for Radio k-Coloring Powers of Paths Having Small Diameter

Year : 2023

Publisher : Springer Science and Business Media Deutschland GmbH

Source Title : Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Document Type :

Abstract

The radio k-chromatic number rck(G) of a graph G is the minimum integer λ such that there exists a function ϕ: V(G) → { 0, 1, ⋯, λ} satisfying | ϕ(u) – ϕ(v) | ≥ k+ 1 – d(u, v), where d(u, v) denotes the distance between u and v. To date, several upper and lower bounds of rck(· ) is established for different graph families. One of the most notable works in this domain is due to Liu and Zhu [SIAM Journal on Discrete Mathematics 2005] whose main results were computing the exact values of rck(· ) for paths and cycles for the specific case when k is equal to the diameter. In this article, we find the exact values of rck(G) for powers of paths where the diameter of the graph is strictly less than k. Our proof readily provides a linear time algorithm for providing such labeling. Furthermore, our proof technique is a potential tool for solving the same problem for other graph classes with “small” diameter.