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

Fujie-Okamoto, Futaba; Renzema, Willem; Zhang, Ping

Math. Bohem. 137, No. 1, 45-63 (2012).

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\).

Reviewer: Ladislav Nebeský (Praha)

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