MATHEMATICA BOHEMICA, Vol. 137, No. 1, pp. 45-63, 2012

# The $k$-metric colorings of a graph

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

Futaba Fujie-Okamoto, Mathematics Department, University of Wisconsin - La Crosse, La Crosse, WI 54601, USA; Willem Renzema, Ping Zhang, Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA

Abstract: For a nontrivial connected graph $G$ of order $n$, the detour distance $D(u,v)$ between two vertices $u$ and $v$ in $G$ is the length of a longest $u-v$ path in $G$. Detour distance is a metric on the vertex set of $G$. For each integer $k$ with $1\le k\le n-1$, a coloring $c V(G)\to\mathbb N$ is a $k$-metric coloring of $G$ if $|c(u)-c(v)|+D(u,v)\ge k+1$ for every two distinct vertices $u$ and $v$ of $G$. The value $\chi_m^k(c)$ of a $k$-metric coloring $c$ is the maximum color assigned by $c$ to a vertex of $G$ and the $k$-metric chromatic number $\chi_m^k(G)$ of $G$ is the minimum value of a $k$-metric coloring of $G$. For every nontrivial connected graph $G$ of order $n$, $\chi_m^1(G)\le\chi_m^2(G)\le\cdots\le\chi_m^{n-1}(G)$. Metric chromatic numbers provide a generalization of several well-studied coloring parameters in graphs. Upper and lower bounds have been established for $\chi_m^k(G)$ in terms of other graphical parameters of a graph $G$ and exact values of $k$-metric chromatic numbers have been determined for complete multipartite graphs and cycles. For a nontrivial connected graph $G$, the anti-diameter $adiam(G)$ is the minimum detour distance between two vertices of $G$. We show that the $adiam(G)$-metric chromatic number of a graph $G$ provides information on the Hamiltonian properties of the graph and investigate realization results and problems on this parameter.

Keywords: detour distance, metric coloring

Classification (MSC 2010): 05C12, 05C15

Full text available as PDF.