A lower bound technique for radio k-coloring

An n-radio k-coloring of a graph G is a function l:V(G)→{0,1,…,n} satisfying the condition |l(u)−l(v)|≥k+1−d(u,v) for all distinct u,v∈V(G). The radio k-chromatic number rck(G) of G is the minimum n such that G admits an n-radio k-coloring. We establish a general technique for computing the lower bound for rck(G) of a general graph G and derive a formula for it. Using this formula we compute lower bounds of rck(⋅) for several graphs and provide alternative short proofs for a number of previously established tight lower bounds. In particular, we progress on a conjecture by Kchikech, Khennoufa and Togni (DMGT 2007) regarding rck(⋅) of infinite paths and reprove a result by Liu and Zhu (SIDMA 2005). We also provide a 43-approximation algorithm for radio labeling regular grid graph of degree 6.