## The $$k$$-metric colorings of a graph.(English)Zbl 1249.05093

In the introduction the authors mention the notion of a $$k$$-radio coloring introduced by G. Chartrand, D. Erwin, P. Zhang, and 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$$.
Again, 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$$.
More 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 G. Chartrand, L. Nebeský and 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$$.
For 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.
Let $$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$$.

### MSC:

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

### Keywords:

detour distance; metric coloring; metric chromatic number

### Citations:

Zbl 0989.05102; Zbl 1056.05054
Full Text: