Radio k-chromatic number of cycles for large k
Nathaniel J. Karst, Joshua Langowitz, Jessica Oehrlein, Denise Sakai Troxell · Discrete Mathematics Algorithms and Applications · 2017
For a positive integer [Formula: see text], a radio k-labeling of a graph [Formula: see text] is a function [Formula: see text] from its vertex set to the non-negative integers such that for all pairs of distinct vertices [Formula: see text] and [Formula: see text], we have [Formula: see text] where [Formula: see text] is the distance between the vertices [Formula: see text] and [Formula: see text] in [Formula: see text]. The minimum span over all radio [Formula: see text]-labelings of [Formula: see text] is called the radio k-chromatic number and denoted by [Formula: see text]. The most extensively studied cases are the classic vertex colorings ([Formula: see text]), [Formula: see text](2,1)-labelings ([Formula: see text]), radio labelings ([Formula: see text], the diameter of [Formula: see text]), and radio antipodal labelings ([Formula: see text]. Determining exact values or tight bounds for [Formula: see text] is often non-trivial even within simple families of graphs. We provide general lower bounds for [Formula: see text] for all cycles [Formula: see text] when [Formula: see text] and show that these bounds are exact values when [Formula: see text].