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.

05C15 Coloring of graphs and hypergraphs