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

Chartrand, Gary; Nebeský, Ladislav; Zhang, Ping

Discuss. Math., Graph Theory 24, No. 1, 5-21 (2004).

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.

Reviewer: Lorenzo Traldi (Easton)

MSC:

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

Keywords:

radio \(k\)-coloring; \(k\)-chromatic number; path