Radio \(k\)-colorings of paths. (English) Zbl 1056.05053

Authors’ abstract: For a connected graph \(G\) of diameter \(d\) and an integer \(k\) with \(1\leq k\leq d\), a radio \(k\)-coloring of \(G\) is an assignment \(c\) of colors (positive integers) to the vertices of \(G\) such that \(d(u,v)+| c(u)-c(v) |\geq 1+k\) for every two distinct vertices \(u\) and \(v\) of \(G\), where \(d(u,v)\) is the distance between \(u\) and \(v\). The value rc\(_k(c)\) of a radio \(k\)-coloring \(c\) of \(G\) is the maximum color assigned to a vertex of \(G\). The radio \(k\)-chromatic number rc\(_k(G)\) of \(G\) is the minimum value of rc\(_k(c)\) taken over all radio \(k\)-colorings \(c\) of \(G\). In this paper, radio \(k\)-colorings of paths are studied. For the path \(P_n\) of order \(n\geq 9\) and \(n\) odd, a new improved bound for rc\(_{n-2}(P_n)\) is presented. For \(n\geq 4\), it is shown that rc\(_{n-3}(P_n)\leq {n-2\choose 2}+2\). Upper and lower bounds are also presented for \(rc_k(P_n)\) in terms of \(k\) when \(1\leq k\leq n-1\). The upper bound is shown to be sharp when \(1\leq k\leq 4\) and \(n\) is sufficiently large.


05C15 Coloring of graphs and hypergraphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C12 Distance in graphs
Full Text: DOI