# zbMATH — the first resource for mathematics

The metric chromatic number of a graph. (English) Zbl 1181.05038
Summary: For a nontrivial connected graph $$G$$, let $$c:V(G)\to\mathbb N$$ be a vertex coloring of $$G$$ where adjacent vertices may be colored the same and let $$V_1,V_2,\dots,V_k$$ be the resulting color classes. For a vertex $$v$$ of $$G$$, the metric color code of $$v$$ is the $$k$$-vector
$\text{code}(v)= (d(v,V_1),d(v,V_2),\dots,d(v,V_k)),$
where $$d(v,V_i)$$ is the minimum distance between $$v$$ and a vertex in $$V_i$$. If $$\text{code}(w)\neq \text{code}(v)$$ for every two adjacent vertices $$u$$ and $$v$$ of $$G$$, then $$c$$ is a metric coloring of $$G$$. The minimum $$k$$ for which $$G$$ has a metric $$k$$-coloring is called the metric chromatic number of $$G$$ and is denoted by $$\mu(G)$$. The metric chromatic numbers of some well-known graphs are determined and characterizations of connected graphs of order $$n$$ having metric chromatic number 2 and $$n-1$$ are established. We present several bounds for the metric chromatic number of a graph in terms of other graphical parameters and study the relationship between the metric chromatic number of a graph and its chromatic number.

##### MSC:
 05C15 Coloring of graphs and hypergraphs