The \(k\)-metric colorings of a graph. (Q2897337)

In the introduction the authors mention the notion of a \(k\)-radio coloring introduced by \textit{G. Chartrand}, \textit{D. Erwin}, \textit{P. Zhang}, and \textit{F. Harary} in [``Radio labelings of graphs,'' Bull. Inst. Comb. Appl. 33, 77--85 (2001; Zbl 0989.05102)]. If \(G\) is a connected graph and \(k\) is an integer such that \(1 \leq k \leq \text{diam}(G)\), where \(\text{diam}(G)\) is the diameter of \(G\), then by a \(k\)-radio coloring of \(G\) is meant an assignment \(c\) of positive integers to vertices of \(G\) such that \(| c(u)-c(v)| +d(u,v)\geq k + 1\), for every two distinct vertices \(u\) and \(v\) of \(G\). NEWLINENEWLINENEWLINENEWLINEAgain, let \(G\) be a connected graph. If \(u, v\in V(G)\), then the detour distance \(D(u,v)\) in \(G\) denotes the length of a longest \(u\)-\(v\) path in \(G\). Note that if \(G\) is a connected graph, then the detour distance is a metric on \(V(G)\). In short, if the distance is replaced by the detour distance in the above cited paper, then we obtain the definition of a \(k\)-metric coloring of \(G\).NEWLINENEWLINENEWLINE NEWLINEMore formally, if \(G\) is a connected graph of order \(n \geq 2\) and \(k\) is an integer such that \(1\leq k\leq n-1\), then by a \(k\)-metric coloring of \(G\) is meant an assignment \(c\) of positive integers to vertices of \(G\) such that \({| c(u)-c(v)| +D(u,v)\geq k+1}\) for every two distinct vertices \(u\) and \(v\) of \(G\). The notion of \(k\)-metric coloring of a connected graph \(G\) is a generalization of the notion of a Hamiltonian coloring of \(G\) introduced by \textit{G. Chartrand}, \textit{L. Nebeský} and \textit{P. Zhang} in [``Hamiltonian colorings of graphs,'' Discrete Appl. Math. 146, No. 3, 257--272 (2005; Zbl 1056.05054)]. A Hamiltonian coloring of a connected graph of \(G\) with \(n \geq 2\) vertices is the same as an \((n-2)\)-metric coloring of \(G\). NEWLINENEWLINENEWLINE NEWLINEFor a connected graph \(G\) of order \(n \geq 2\) and for a positive integer \(k\), \(1\leq k\leq n-1\), the notion of \(k\)-metric chromatic number \(\chi ^k_m\) is derived from the notion of \(k\)-metric coloring of \(G\) in the expected way. The \(k\)-metric chromatic number \(\chi ^k_m\) for graphs of some kinds, including cycles, are determined in this paper. NEWLINENEWLINENEWLINE NEWLINELet \(G\) be a connected graph with \(n \geq 2\) vertices. The minimum detour distance between two distinct vertices of \(G\), the anti-diameter of \(G\), is denoted by \(\text{adiam}(G)\). Put \(a=\text{adiam}(G)\). In the last part of the paper, \(\chi ^a_m(G)\) is studied. At least one result for an illustration only: a connected graph \(G\) of order \(n \geq 2\) is Hamiltonian-connected if and only if \(\chi ^a_m(G)=n\).