The metric chromatic number of a graph.
Gary Chartrand, Futaba Okamoto, Ping Zhang · 2009
For a nontrivial connected graph G, let c: V (G) → N be a vertex coloring of G where adjacent vertices may be colored the same and let V1,V2,...,Vk be the resulting color classes. For a vertex v of G, the metric color code of v is the k-vector code(v) =(d(v, V1),d(v, V2), ·· ·,d(v, Vk)), where d(v, Vi) is the minimum distance between v and a vertex in Vi. If code(u) = code(v) for every two adjacent vertices u and v of G, thenc 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 μ(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.