  Graph colorings is a fundamental topic in graph theory that require an
assignment of labels (or colors) to vertices or edges subject to various
constraints. We focus on the harmonious coloring of a graph, which is a proper
vertex coloring such that for every two distinct colors i, j at most one pair
of adjacent vertices are colored with i and j. This type of coloring is
edge-distinguishing and has potential applications in transportation network,
computer network, airway network system.
  The results presented in this paper fall into two categories: in the first
part of the paper we are concerned with the computational aspects of finding a
minimum harmonious coloring and in the second part we determine the exact value
of the harmonious chromatic number for some particular graphs and classes of
graphs. More precisely, in the first part we show that finding a minimum
harmonious coloring for arbitrary graphs is APX-hard, the natural greedy
algorithm is a $\Omega(\sqrt{n})$-approximation, and, moreover, we show a
relationship between the vertex cover and the harmonious chromatic number. In
the second part we determine the exact value of the harmonious chromatic number
for all 3-regular planar graphs of diameter 3, some non-planar regular graphs
and cycle-related graphs.
