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.
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
