查看文章

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 r c k (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 r c k (G) of a general graph G and derive a formula for it. Using this formula we compute lower bounds of r c k (⋅) 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 r c k (⋅) of infinite paths and reprove a result by Liu and Zhu (SIDMA 2005). We also provide a 4 3-approximation algorithm for radio labeling regular grid graph of degree 6.