A lower bound for radio ?-chromatic number of an arbitrary graph

Abstract

Radio ?-coloring is a variation of Hale's channel assignment problem, in which one seeks to assign positive integers to the vertices of a graph G, subject to certain constraints involving the distance be- tween the vertices. Speciffically, for any simple connected graph G with diameter d and a positive integer ?, 1 ? ? ? d, a radio ?-coloring of G is an assignment f of positive integers to the vertices of G such that jf(u)-f(v)j ? 1+?-d(u; v), where u and v are any two distinct vertices of G and d(u; v) is the distance between u and v. In this paper we give a lower bound for the radio ?-chromatic number of an arbitrary graph in terms of k, the total number of vertices n and a positive integer M such that d(u; v)+d(v;w)+d(u;w) ? M for all u; v;w 2 V (G). If M is the triameter we get a better lower bound. We also ffind the triameter M for several graphs, and show that the lower bound obtained for these graphs is sharp for the case ? = d. 2015 University of Calgary.